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?
Initially, each node points to itself (each node is its own parent).
If a union operation has been performed, some nodes may now have a different parent.
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);
}# Python implementation of find operation
def find(x, parent):
if parent[x] == x:
return x
return find(parent[x], parent)// JavaScript implementation of find operation
function find(x, parent) {
if (parent[x] === 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?
Find the roots of both sets (using the find operation).
- If the roots are different, merge the sets by attaching one root to the other.
If the roots are different, merge the sets by attaching one root to the other.
- If the roots are different, merge the sets by attaching one root to the other.
If the roots are different, merge the sets by attaching one root to the other.
- 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;
}
}# Python implementation of union operation
def union(a, b, parent):
a_parent = find(a, parent)
b_parent = find(b, parent)
if a_parent != b_parent:
parent[b_parent] = a_parent// JavaScript implementation of union operation
function union(a, b, parent) {
const a_parent = find(a, parent);
const 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<<" ";
}
}# Python DSU implementation
def find(x, parent):
if parent[x] == x:
return x
return find(parent[x], parent)
def union(a, b, parent):
a_parent = find(a, parent)
b_parent = find(b, parent)
if a_parent != b_parent:
parent[b_parent] = a_parent
# Main code
n = 5 # Number of elements
parent = [i for i in range(n)] # Initialize parent array
union(0, 1, parent)
union(3, 4, parent)
union(0, 3, parent)
print(parent) # Show the final parent array// JavaScript DSU implementation
function find(x, parent) {
if (parent[x] === x) return x;
return find(parent[x], parent);
}
function union(a, b, parent) {
const a_parent = find(a, parent);
const b_parent = find(b, parent);
if (a_parent !== b_parent) {
parent[b_parent] = a_parent;
}
}
// Main code
const n = 5; // Number of elements
const parent = Array.from({length: n}, (_, i) => i); // Initialize parent array
union(0, 1, parent);
union(3, 4, parent);
union(0, 3, parent);
console.log(parent); // Show the final parent arrayOptimization
How is this guide?