...

/

Disjoint Set Union Data Structure

Disjoint Set Union Data Structure

Study the implementation of a DSU data structure.

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.

Press + to interact
#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) ...