AdvancedData Structures & Algorithms · Lesson 32 of 40 · Updated ·
Union-Find (Disjoint Set Union) — Path Compression, Union by Rank and Uses
On the first day of college, 600 students know nobody. Then friendships form: "Asha and Ravi are friends", "Ravi and Meena are friends". At any moment the principal may ask, "Are Asha and Meena in the same friend circle?" or "How many separate circles are there now?" Running BFS after every new friendship would be slow. Union-Find, also called Disjoint Set Union (DSU), handles both questions in nearly O(1) each.
1. The idea: every group has a leader
Each group (set) is stored as a small tree. Every element points to a parent; the element at the top of the tree points to itself and is the group's root (leader). Two elements are in the same group exactly when they have the same root.
Only two operations are needed:
- find(x) — follow parent pointers up to the root and return it.
- union(a, b) — find both roots; if they differ, make one root the parent of the other. The two groups are now one.
At the start, every element is its own group: parent[i] = i.
2. Two tricks that make it fast
Without care, the trees can become long chains, and find becomes O(n). Two small tricks fix this.
Path compression. During find(x), after finding the root, point every node on the path directly at the root. The next find on any of them takes one step.
Union by rank. When joining two trees, attach the shorter tree under the root of the taller one, so the height does not grow. rank is an upper bound on the tree's height. (Union by size — attach the smaller group under the larger — works just as well and also tells you group sizes.)
With both tricks, a sequence of m operations takes O(m · α(n)), where α is the inverse Ackermann function. α(n) is at most 4 for any n you will ever meet, so in practice each operation is constant time.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.groups = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already in the same group
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra # ra is the taller tree
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
self.groups -= 1
return True
d = DSU(6)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (0, 2)]:
print(f"union({a},{b}) ->", d.union(a, b), d.parent)
print("same(1, 2)?", d.find(1) == d.find(2), " same(3, 4)?", d.find(3) == d.find(4))
print("groups:", d.groups)
union(0,1) -> True [0, 0, 2, 3, 4, 5]
union(2,3) -> True [0, 0, 2, 2, 4, 5]
union(1,3) -> True [0, 0, 0, 2, 4, 5]
union(4,5) -> True [0, 0, 0, 2, 4, 4]
union(0,2) -> False [0, 0, 0, 2, 4, 4]
same(1, 2)? True same(3, 4)? False
groups: 2
Notice parent[3] is still 2, not 0. Path compression is lazy: it only flattens a path when someone calls find on it.
For very deep trees, a recursive find can hit Python's recursion limit. An iterative version first walks to the root, then walks the path again to re-point each node.
3. Union by size in Java
public class Main {
static int[] parent, size;
static int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != root) { // second pass: compress the path
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra; // smaller group goes under the larger
size[ra] += size[rb];
return true;
}
public static void main(String[] args) {
int n = 7;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
int[][] friends = {{0, 1}, {1, 2}, {3, 4}, {5, 6}, {4, 6}};
for (int[] f : friends) union(f[0], f[1]);
System.out.println("size of 0's circle = " + size[find(0)]);
System.out.println("size of 3's circle = " + size[find(3)]);
System.out.println("0 and 5 together? " + (find(0) == find(5)));
}
}
size of 0's circle = 3
size of 3's circle = 4
0 and 5 together? false
The iterative find cannot overflow the stack, which matters when n is around 10⁵ or more.
4. What Union-Find is used for
| Problem | How DSU helps |
|---|---|
| Number of connected components / friend circles | start with n groups; every successful union lowers the count by 1 |
| Detect a cycle in an undirected graph | an edge whose ends are already in the same group closes a cycle |
| Kruskal's minimum spanning tree | take an edge only if union returns True |
| Redundant connection | the first edge for which union returns False |
| Accounts merge, similar strings | union items that share an email or are "similar", then group by root |
| Number of islands as land is added | each new land cell unions with its land neighbours |
def find(parent, x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving, a simple compression
x = parent[x]
return x
def first_cycle_edge(n, edges):
parent = list(range(n))
for u, v in edges:
ru, rv = find(parent, u), find(parent, v)
if ru == rv:
return (u, v) # u and v were already connected
parent[ru] = rv
return None
print(first_cycle_edge(4, [(0, 1), (1, 2), (2, 3), (3, 1)]))
print(first_cycle_edge(4, [(0, 1), (1, 2), (2, 3)]))
(3, 1)
None
Limits: DSU only merges. It cannot split a group or remove an edge, and it does not find the actual path between two elements. It also does not detect cycles in directed graphs — use DFS colours or Kahn's algorithm for that.
Common mistakes
- Comparing
parent[a] == parent[b]instead offind(a) == find(b). Two elements can share a root without sharing a direct parent. - In
union, linkingatobinstead of root to root:parent[find(a)] = find(b). - Forgetting to initialise
parent[i] = i. - Using DSU for directed-graph cycles or for problems where connections are removed.
- Writing a recursive
findwithout compression on large inputs, which is slow and can overflow the stack.
Quick recap
- Each group is a tree; the root is the leader;
findclimbs to the root,unionlinks two roots. - Path compression flattens paths during
find; union by rank or size keeps trees short. - With both, each operation is effectively O(1) (O(α(n)) amortised).
- Uses: counting components, undirected cycle detection, Kruskal's MST, merging accounts.
- It can only merge, never split.