Start here
Union-Find maintains a collection of non-overlapping sets and supports two operations: find(x) — which set does x belong to? — and union(a, b) — merge the two sets containing a and b.
The Structure
Each set is stored as a tree, with every element pointing to a parent. The root represents the whole set. Two elements are in the same set exactly when they have the same root.
Union is therefore trivial: point one root at the other. All the difficulty is in keeping find fast, because it must walk to the root.
Optimisation 1: Union by Rank
Naively linking roots can build a long chain — press Build a bad chain with both optimisations off to see one. Depth grows to n and every find becomes O(n).
Union by rank always attaches the
shorter tree under the taller one. The result never gets deeper than necessary, keeping depth at O(log n). Toggle the checkbox and rebuild the chain to compare.
Optimisation 2: Path Compression
When find(x) walks to the root, it already knows the answer for every node along the way — so it re-points them all directly at the root on the way back.
Press Find on a deep node with compression on and watch the tree flatten in a single operation. Each find makes all subsequent finds cheaper, so the cost is amortised away.
The Famous Complexity
With both optimisations, m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that for any n that fits in the observable universe, α(n) < 5.
It is not technically constant, but it is constant for every practical purpose — one of the most striking results in data-structure analysis.
Where It Is Used
- Kruskal's MST — sort edges, add one if its endpoints are in different sets. Union-Find is what makes the cycle check fast.
- Connected components — in a graph, an image (flood fill), or a network.
- Percolation and clustering — does a path exist from top to bottom?
- Account or record merging — treating "these two IDs are the same person" as a union.
Tracking which things are connected
Union-Find (a disjoint-set union structure) answers one question extremely fast: are these two elements in the same group? And it supports merging groups.
Two operations:
find(x) — return a representative of x's set. union(x, y) — merge the sets containing x and y.
Two elements are connected exactly when find(x) == find(y).
Each set is stored as a tree, with every element pointing at its parent and the root representing the set. The root points to itself.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # each element its own root
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already connected
if self.rank[rx] < self.rank[ry]: # union by rank
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
Why the two optimisations matter
Without them, the trees can degenerate into chains and find becomes O(n). Two techniques together make it effectively constant.
Union by rank (or by size) always attaches the shorter tree under the taller one, so depth grows logarithmically at worst rather than linearly.
Path compression flattens the tree during find: every node on the path is re-pointed closer to the root, so subsequent finds are shorter. The line self.parent[x] = self.parent[self.parent[x]] is path halving — simpler than full compression and just as effective in practice.
Together they give an amortised complexity of O(α(n)), where α is the inverse Ackermann function. For any n that fits in the universe, α(n) < 5 — so it is constant for all practical purposes.
| Optimisations | Complexity per operation |
|---|
| Neither | O(n) |
| Union by rank only | O(log n) |
| Path compression only | O(log n) amortised |
| Both | O(α(n)) — effectively O(1) |
That is one of the most striking results in data structures: two short additions to an obvious algorithm take it from linear to essentially constant.
Kruskal's algorithm, the canonical use
Union-Find exists largely because of this. Kruskal's minimum spanning tree algorithm sorts all edges by weight and adds each one unless it would form a cycle — and "would form a cycle" means "both endpoints are already connected".
def kruskal(n, edges):
uf = UnionFind(n)
mst, total = [], 0
for weight, u, v in sorted(edges):
if uf.union(u, v): # False if already connected
mst.append((u, v, weight))
total += weight
return mst, total
The union returning False is the cycle check. There is no separate cycle detection, because Union-Find already knows.
O(E log E) for the sort, plus effectively O(E) for the unions — so sorting dominates, and the connectivity bookkeeping is free.
What the two optimisations are actually worth
Union-Find is a handful of lines, and then two optimisations turn its near-linear complexity from a claim into a fact. Both are one line each, so the honest way to judge them is to count pointer hops with each combination switched on and off.
Guided tour
- Union a few pairs and watch separate trees form. The group counter drops by one per successful merge.
- Union two elements already in the same set. Nothing changes — and that check is exactly how Kruskal avoids creating a cycle.
- Turn off both optimisations and press Build a bad chain. Depth grows linearly and finds get slow.
- Turn path compression back on and run Find on the deepest node. The tree flattens in one step.
- Compare max depth with rank on and off. Union by rank prevents the tall trees; compression fixes the ones already made.
Worth remembering
Union-Find answers "same group?" and "merge groups" in effectively constant time, using union by rank to keep trees shallow and path compression to flatten them on the way. It is the structure that makes Kruskal's algorithm and fast connected-component queries possible.
Where else it is used
- Connected components in a static or growing graph — union every edge, then count distinct roots.
- Cycle detection in an undirected graph. A union that returns False means the edge closes a cycle.
- Percolation and network reliability — adding links and asking when the network becomes connected.
- Image segmentation — merging adjacent similar pixels into regions.
- Least common ancestor offline (Tarjan's algorithm).
- Equivalence classes — type unification in compilers, merging duplicate records in entity resolution.
- Grid problems — counting islands, or determining when a path exists across a grid as cells are opened.
The grid case is a good example of the structure's fit: cells are unioned as they are opened, and asking whether the top and bottom are connected is one find comparison. Re-running BFS after each change would be far more expensive.
What it cannot do
The critical limitation: Union-Find supports merging, not splitting. There is no efficient disconnect(x, y).
That is because path compression destroys the tree's original shape — the structure knows which elements are together and not how they came to be, so it cannot undo a union.
Consequences:
Dynamic connectivity with deletions needs a different structure (link-cut trees, or offline processing).
Time-travel queries — "were these connected at step k?" — need a persistent or rollback variant. A rollback version exists, and it must forgo path compression, giving O(log n) instead.
Directed connectivity is not what it does. Union-Find handles undirected, symmetric relationships; strongly connected components need Tarjan's or Kosaraju's algorithm.
| Need | Structure |
|---|
| Merge groups, test membership | Union-Find |
| Deletions as well | Link-cut trees, or offline |
| Directed reachability | DFS, transitive closure |
| Shortest paths | BFS or Dijkstra |
| Component sizes | Union-Find with a size array |
Practical variations
Tracking component sizes. Keep a size array updated on union. Useful for "largest component" queries and for union by size, which performs comparably to union by rank.
Counting components. Start at n and decrement on each successful union. One integer, and it answers "is the graph connected yet?" in O(1).
Weighted Union-Find. Store an offset alongside each parent pointer to maintain relative values — used for problems involving equations between variables, or relative positions.
Union-Find on arbitrary keys. Replace the arrays with dictionaries so elements need not be integers 0..n−1.
Questions people ask
What does O(α(n)) mean? The inverse Ackermann function, below 5 for any conceivable n. Treat it as constant.
Can I undo a union? Not with path compression. A rollback variant exists without it, at O(log n).
Union by rank or by size? Both work and give the same complexity. Size is slightly more intuitive and lets you query component sizes for free.
Does it work for directed graphs? No — it models symmetric connectivity only.
Why does path compression not break correctness? Because only the root identifies the set, and re-pointing nodes closer to the same root changes nothing about membership.
How does it compare with BFS for connectivity? BFS answers one query in O(V+E). Union-Find answers many queries on a growing graph in near-constant time each.
Recap in one screen
find returns a set's representative; union merges two sets; equality of representatives means connected.- Union by rank keeps trees shallow; path compression flattens them during
find. - Together they give amortised O(α(n)) — effectively constant for any real input.
- Kruskal's MST algorithm is the canonical use, where
union returning False is the cycle check. - It supports merging only — no efficient deletion, and no directed reachability.