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 representativeiota(this->parents.begin(), this->parents.end(), 0);}int find(int u) {// find the rootint root = u;while (this->parents[root] != root) { root = this->parents[root]; }// compress pathswhile (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 setif (u == v) { return; }// union by rank -> the root with greater rank becomes the new rootif (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 ...