Union-Find, also called Disjoint Set Union (DSU), is a data structure that tracks a collection of elements partitioned into non-overlapping groups. It supports two operations: find, which returns the representative of an element’s group, and union, which merges two groups. With two optimizations, path compression and union by rank or size, both operations run in near-constant amortized time.
When to use it#
Reach for Union-Find when a problem is about connectivity or grouping: which items belong to the same component, how many distinct groups exist, or whether adding an edge creates a cycle in an undirected graph. It shines when connections arrive incrementally and you need fast merge and query, where a repeated graph traversal would be too slow.
Worked example#
A compact implementation with path compression and union by rank:
1class UnionFind:
2 def __init__(self, n):
3 self.parent = list(range(n))
4 self.rank = [0] * n
5
6 def find(self, x):
7 while self.parent[x] != x:
8 self.parent[x] = self.parent[self.parent[x]] # path compression
9 x = self.parent[x]
10 return x
11
12 def union(self, a, b):
13 ra, rb = self.find(a), self.find(b)
14 if ra == rb:
15 return False # already connected, an edge here forms a cycle
16 if self.rank[ra] < self.rank[rb]:
17 ra, rb = rb, ra
18 self.parent[rb] = ra
19 if self.rank[ra] == self.rank[rb]:
20 self.rank[ra] += 1
21 return True
Complexity#
With both optimizations, each find and union runs in O(alpha(n)) amortized time, where alpha is the inverse Ackermann function and is effectively constant for any realistic input. Space is O(n) for the parent and rank arrays.
Practice problems#
- Number of Connected Components in an Undirected Graph
- Redundant Connection
- Number of Provinces
- Accounts Merge
- Graph Valid Tree
- Number of Islands (union-find variant)
For dependency ordering on directed graphs rather than undirected grouping, see topological sort. Back to the pattern hub.