Disjoint Set Union (DSU) / Union-Find
Disjoint Set Union (DSU) / Union-Find
Disjoint Set Union (DSU), also called Union-Find, is a powerful data structure that efficiently tracks a collection of elements partitioned into non-overlapping (disjoint) sets. It answers two questions in nearly O(1) time:
- Find: Which set does this element belong to?
- Union: Merge two sets together.
Video Explanation
🧠 Real-World Analogy
Think of students in different friend groups:
Initially everyone is their own group:
{Alice} {Bob} {Charlie} {David} {Eve}
After Alice and Bob become friends → Union(Alice, Bob):
{Alice, Bob} {Charlie} {David} {Eve}
After Charlie and David become friends → Union(Charlie, David):
{Alice, Bob} {Charlie, David} {Eve}
After Bob and Charlie become friends → Union(Bob, Charlie):
{Alice, Bob, Charlie, David} {Eve}
Are Alice and David in the same group? → Find(Alice) == Find(David)? → YES ✅
Are Alice and Eve in the same group? → Find(Alice) == Find(Eve)? → NO ❌
🐢 Naive Implementation (Without Optimizations)
Each element points to a parent. The root of the tree is the representative of the set.
Initial state: parent[i] = i (everyone is their own parent)
Elements: 0 1 2 3 4
parent: 0 1 2 3 4
Union(0,1): parent[1] = 0
0 1 2 3 4
|
1
Union(1,2): parent[2] = 1
0
|
1
|
2
Union(2,3): parent[3] = 2
0
|
1
|
2
|
3
⚠️ Problem: Tree becomes a chain → Find() takes O(n) per call!
⚡ Optimization 1: Union by Rank
Idea: Always attach the shorter tree under the taller tree to keep the tree flat.
Union by Rank — always attach smaller rank under larger rank:
rank[0]=0 rank[1]=0 rank[2]=0 rank[3]=0
Union(0,1): rank equal → make 0 root of 1, rank[0]++
0(rank=1)
|
1(rank=0)
Union(2,3): rank equal → make 2 root of 3, rank[2]++
2(rank=1)
|
3(rank=0)
Union(0,2): rank equal → make 0 root of 2, rank[0]++
0(rank=2)
/ \
1 2(rank=1)
|
3
Tree stays BALANCED → max height = O(log n)
⚡ Optimization 2: Path Compression
Idea: When we call Find(x), make every node on the path point directly to the root. This flattens the tree for all future calls.
Before Path Compression:
Find(3) traverses: 3 → 2 → 0 (root)
0
|
2
|
3
After Path Compression (Find(3)):
All nodes on path now point directly to root 0:
0
/|\
1 2 3 ← 3 now points directly to 0!
Next Find(3) = O(1) ✅
🔥 Combined: Path Compression + Union by Rank
This gives nearly O(1) amortized time per operation — the most efficient possible.
Time Complexity: O(α(n)) per operation
where α = inverse Ackermann function ≈ constant (≤ 5) for all practical inputs
💻 Full Implementation
- Python
- Java
- C++
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # parent[i] = i initially
self.rank = [0] * n # rank[i] = 0 initially
def find(self, x):
# Path Compression: point directly to root
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Union by Rank: attach smaller rank under larger rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True # Successfully merged
def connected(self, x, y):
return self.find(x) == self.find(y)
# Example Usage
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(2, 3)
dsu.union(1, 2)
print(dsu.connected(0, 3)) # True → 0-1-2-3 all connected
print(dsu.connected(0, 4)) # False → 4 is isolated
public class DSU {
private int[] parent;
private int[] rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i; // each element is its own parent
rank[i] = 0;
}
}
// Find with Path Compression
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// Union with Union by Rank
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false; // already in same set
// Attach smaller rank under larger rank
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true; // successfully merged
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
DSU dsu = new DSU(5);
dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(1, 2);
System.out.println(dsu.connected(0, 3)); // true
System.out.println(dsu.connected(0, 4)); // false
}
}
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;
class DSU {
public:
vector<int> parent, rank_;
DSU(int n) {
parent.resize(n);
rank_.resize(n, 0);
iota(parent.begin(), parent.end(), 0); // parent[i] = i
}
// Find with Path Compression
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// Union with Union by Rank
bool union_(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false; // already in same set
// Attach smaller rank under larger rank
if (rank_[rootX] < rank_[rootY]) {
parent[rootX] = rootY;
} else if (rank_[rootX] > rank_[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank_[rootX]++;
}
return true; // successfully merged
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};
int main() {
DSU dsu(5);
dsu.union_(0, 1);
dsu.union_(2, 3);
dsu.union_(1, 2);
cout << dsu.connected(0, 3) << endl; // 1 (true)
cout << dsu.connected(0, 4) << endl; // 0 (false)
return 0;
}
🔍 Step-by-Step Dry Run
n=6, Elements: 0 1 2 3 4 5
Initial: parent=[0,1,2,3,4,5] rank=[0,0,0,0,0,0]
─────────────────────────────────────────────
Union(0, 1):
find(0)=0, find(1)=1
rank equal → parent[1]=0, rank[0]=1
parent=[0,0,2,3,4,5] rank=[1,0,0,0,0,0]
0(rank=1)
|
1
─────────────────────────────────────────────
Union(2, 3):
find(2)=2, find(3)=3
rank equal → parent[3]=2, rank[2]=1
parent=[0,0,2,2,4,5] rank=[1,0,1,0,0,0]
0(rank=1) 2(rank=1)
| |
1 3
─────────────────────────────────────────────
Union(4, 5):
find(4)=4, find(5)=5
rank equal → parent[5]=4, rank[4]=1
parent=[0,0,2,2,4,4] rank=[1,0,1,0,1,0]
0(rank=1) 2(rank=1) 4(rank=1)
| | |
1 3 5
─────────────────────────────────────────────
Union(0, 2):
find(0)=0, find(2)=2
rank[0]=1 == rank[2]=1 → parent[2]=0, rank[0]=2
parent=[0,0,0,2,4,4] rank=[2,0,1,0,1,0]
0(rank=2)
/ \
1 2(rank=1)
|
3
─────────────────────────────────────────────
Union(0, 4):
find(0)=0, find(4)=4
rank[0]=2 > rank[4]=1 → parent[4]=0
parent=[0,0,0,2,0,4] rank=[2,0,1,0,1,0]
0(rank=2)
/ | \
1 2 4(rank=1)
| |
3 5
─────────────────────────────────────────────
Find(5) with Path Compression:
5 → parent[5]=4 → parent[4]=0 (root!)
Path compress: parent[5] = 0 directly!
parent=[0,0,0,2,0,0]
0(rank=2)
/ | \ \
1 2 4 5 ← 5 now points directly to 0!
|
3
─────────────────────────────────────────────
connected(3, 5)?
find(3): 3→2→0 (root), path compress → parent[3]=0
find(5): 5→0 (root, already compressed)
find(3)==find(5) → 0==0 → TRUE ✅
🌍 Classic Application: Cycle Detection in Graph
Problem: Given edges [(0,1),(1,2),(2,0)], detect if there's a cycle.
DSU = {0,1,2} initially
Edge(0,1): find(0)=0, find(1)=1 → different → union → no cycle
Edge(1,2): find(1)=0, find(2)=2 → different → union → no cycle
Edge(2,0): find(2)=0, find(0)=0 → SAME ROOT → CYCLE DETECTED! 🔴
- Python
- Java
- C++
def has_cycle(n, edges):
dsu = DSU(n)
for u, v in edges:
if not dsu.union(u, v):
return True # same component → cycle!
return False
print(has_cycle(3, [(0,1),(1,2),(2,0)])) # True
print(has_cycle(3, [(0,1),(1,2)])) # False
public class GraphCycleDetector {
public static boolean hasCycle(int n, int[][] edges) {
DSU dsu = new DSU(n);
for (int[] edge : edges) {
if (!dsu.union(edge[0], edge[1])) {
return true; // same component → cycle!
}
}
return false;
}
}
bool hasCycle(int n, vector<pair<int,int>>& edges) {
DSU dsu(n);
for (auto& [u, v] : edges) {
if (!dsu.union_(u, v)) {
return true; // same component → cycle!
}
}
return false;
}
⚡ Brute Force vs DSU
Problem: Check if nodes A and B are connected after Q union operations
❌ BRUTE FORCE (BFS/DFS each time):
Each query: O(V + E)
Q queries: O(Q × (V + E))
For Q=10⁵, V=10⁵ → 10¹⁰ operations → TLE ❌
✅ DSU with Path Compression + Union by Rank:
Each union/find: O(α(n)) ≈ O(1)
Q queries: O(Q × α(n)) ≈ O(Q)
For Q=10⁵ → 10⁵ operations → Fast ✅
📊 Complexity Summary
| Operation | Naive DSU | Union by Rank only | Path Compression only | Both Optimizations |
|---|---|---|---|---|
| Find | O(n) | O(log n) | O(log n) amortized | O(α(n)) ≈ O(1) |
| Union | O(n) | O(log n) | O(log n) amortized | O(α(n)) ≈ O(1) |
| Space | O(n) | O(n) | O(n) | O(n) |
α(n) = Inverse Ackermann function. For all practical values of n (up to 10^80), α(n) ≤ 5.
❌ Common Mistakes
- Not using Path Compression — Without it, Find() degrades to O(n) for skewed trees.
- Not using Union by Rank — Leads to unbalanced trees even with path compression.
- Forgetting to check if already connected before union — Always check
find(x) == find(y)first to avoid redundant merges. - Using 1-indexed elements with 0-indexed parent array — Initialize
parentof sizen+1if elements are 1-indexed. - Modifying rank incorrectly — Only increment rank when two trees of equal rank merge.
🏋️ Practice Problems
| # | Problem | Concept | Difficulty |
|---|---|---|---|
| 1 | Number of Connected Components in Graph | Basic DSU | 🟢 Easy |
| 2 | Find if Path Exists in Graph | Basic DSU | 🟢 Easy |
| 3 | Redundant Connection | Cycle Detection | 🟡 Medium |
| 4 | Number of Provinces | Connected Components | 🟡 Medium |
| 5 | Accounts Merge | DSU with strings | 🟡 Medium |
| 6 | Most Stones Removed with Same Row or Column | DSU on coordinates | 🟡 Medium |
| 7 | Satisfiability of Equality Equations | DSU on characters | 🟡 Medium |
| 8 | Kruskal's Minimum Spanning Tree | DSU + Greedy | 🔴 Hard |
| 9 | Swim in Rising Water | DSU + Binary Search | 🔴 Hard |
🌍 Real-World Applications
- Network connectivity — Check if two computers are in the same network
- Kruskal's MST algorithm — Build minimum spanning tree by adding edges without creating cycles
- Image segmentation — Group pixels belonging to the same region
- Social networks — Friend circle / community detection
- Compiler optimization — Pointer analysis / Alias analysis (e.g., Steensgaard's algorithm) to group aliased variables
🔗 Related Topics
- Dijkstra's Algorithm: Shortest path algorithm for non-negative weighted graphs ().
- Segment Tree: Advanced tree structure for range queries and updates ().
- Trie: Prefix tree for efficient string matching and autocomplete ().
🔗 References
🧠 Quick Quiz
Test Your Understanding
Answer these 3 questions to check what you have learned.
Q1
What is the main topic of this documentation page?
Q2
What should be identified before implementing disjoint set union?
Q3
How is understanding of disjoint set union best checked?
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Disjoint Set Union (DSU) / Union-Find"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.