DSA · Chapter 30 of 40
Union-Find (Disjoint Set)
Union-find tracks a collection of disjoint sets with two operations: find (which set does x belong to?) and union (merge two sets). With path compression and union by rank both run in almost O(1) amortised time.
It is the tool for connectivity questions: number of islands by merging, cycle detection in undirected graphs, and Kruskal's MST.
Path compression
During find, point every node visited directly at the root, which flattens the tree for later queries.
Union by rank/size
Attach the smaller tree under the larger one so the structure stays shallow.
Example 1 (python)
parent = list(range(5))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
union(0, 1)
union(1, 2)
print(find(0) == find(2))Output
True0, 1 and 2 are now in the same set.
Example 2 (python)
# count components after unions
print(len({find(i) for i in range(5)}))Output
3Distinct roots equal the number of disjoint sets.
Key points
- find and union are near O(1) amortised with optimisations.
- Path compression flattens the tree.
- Union by rank keeps trees shallow.
- Used for connectivity, cycles and Kruskal's MST.
💡 Note: Counting distinct roots is the standard way to count connected components.