Disjoint Set Union
An algorithm that merges vertices into sets and efficiently tracks their connectivity
Disjoint Set Union also know as Union Find is an algorithm that helps manage elements organized into non-overlapping (disjoint) sets. It supports two primary operations Union and Find.
Operations on Disjoint Set Union
Union
Union operation merges two sets to form a single set.
Find
Find operation returns the representative (or parent) of the set.
How Find Operation Works?
1
Initially, each node points to itself (each node is its own parent).
2
If a union operation has been performed, some nodes may now have a different parent.
3
To find the root of a node, we keep following the parent pointers until we reach a node whose parent is itself (the root).
Implementation: Find Operation
//findoperation.cpp
int find(int x,vector<int>&parent){
if(x==parent[x]) return x;
return find(parent[x],parent);
}
Time Complexity
Worst Case: O(n), If unions are done in a non-optimal way, DSU can form a long chain (linked list).
Best Case:O(1), When all nodes already point to the root directly.
How Union Operation Works?
1
Find the roots of both sets (using the find operation).
2
If the roots are different, merge the sets by attaching one root to the other.
Implementation: Union Operation
//unionoperation.cpp
void Union(int a,int b,vector<int>&parent){
int a_parent=find(a,parent);
int b_parent=find(b,parent);
if(a_parent!=b_parent){
parent[b_parent]=a_parent;
}
}
Implementation of DSU
//dsu.cpp
#include<iostream>
#include<vector>
using namespace std;
//findoperation
int find(int x,vector<int>&parent){
if(x==parent[x]) return x;
return find(parent[x],parent);
}
//unionoperation
void Union(int a,int b,vector<int>&parent){
int a_parent=find(a,parent);
int b_parent=find(b,parent);
if(a_parent!=b_parent){
parent[b_parent]=a_parent;
}
}
int main(){
int n;
cin>>n;
vector<int> parent(n);
for(int i=0;i<n;i++){
parent[i]=i;
}
Union(0,1,parent);
Union(3,4,parent);
Union(0,3,parent);
for(int &ele:parent){
cout<<ele<<" ";
}
}