Search⌘ K

Disjoint Set Union Data Structure

Explore the Disjoint Set Union data structure to understand how it supports dynamic connectivity in graphs. Learn how path compression and union by rank optimize the find and unite operations for near-constant time performance, crucial for algorithms like Kruskal's minimum spanning tree.

We'll cover the following...

The following code snippet contains an implementation of a Disjoint Set Union data structure as it’s used in the Implementation of Kruskal’s algorithm.

C++ 17
#include <vector>
#include <numeric>
using namespace std;
class DisjointSetUnion {
private:
vector<int> parents;
vector<int> ranks;
public:
DisjointSetUnion(int numberOfSets) {
this->parents = vector<int>(numberOfSets);
this->ranks = vector<int>(numberOfSets);
// every elements starts as its own parent -- and representative
iota(this->parents.begin(), this->parents.end(), 0);
}
int find(int u) {
// find the root
int root = u;
while (this->parents[root] != root) { root = this->parents[root]; }
// compress paths
while (this->parents[u] != root) {
int tmp = this->parents[u];
this->parents[u] = root;
u = tmp;
}
return root;
}
void unite(int u, int v) {
u = this->find(u);
v = this->find(v);
// u and v are already in the same set
if (u == v) { return; }
// union by rank -> the root with greater rank becomes the new root
if (this->ranks[u] == this->ranks[v]) {
this->parents[u] = v;
this->ranks[v]++;
} else if (this->ranks[u] < this->ranks[v]) {
this->parents[u] = v;
} else if (this->ranks[u] > this->ranks[v]){
this->parents[v] = u;
}
}
};

The sets are represented as trees where the root of each tree is the representative of the set, returned by find. To ensure O(1)\mathcal{O}(1) ...