Disjoint Set in C++
There is no STL library in C++ for using the disjoint set data structures which can be used predominantly for problems like finding minimum spanning trees, cycle detection algorithms, Minimum set problem etc.
I have implemented the data structure which can be used directly while making the focus on the algorithmic logic. This is tested and used code.
It is optimized and incorporates two prominant optimizations i.e. union by rank and path compression.
class disjoint_set {
int size;
vector<int> parent;
vector<int> rank; //Height of each vertex is saved
public :
disjoint_set(int siz) : size(siz){
parent.resize(size);
rank.resize(size);
for(int i=0; i < size; ++i) {
parent[i]=i;
rank[i]=1;
}
}
bool do_union(int u, int v) {
int p1 = find(u);
int p2 = find(v);
if(p1 == p2)
return false; //Already in same set
//Union by rank
if (rank[p1] >= rank[p2]) {
parent[p2] = p1;
rank[p1] = std::max(rank[p1], 1 + rank[p2]);
rank[p2] = rank[p1];
} else {
parent[p1] = p2;
rank[p2] = std::max(rank[p2], 1 + rank[p1]);
rank[p1] = rank[p2];
}
return true;
}
//Return the parent of vertex v
int find(int v) {
if(v == parent[v])
return v;
else {
int p = find(parent[v]);
parent[v]=p; //Path compression
return p;
}
}
};
