Union-Find (also called Disjoint Set Union, or DSU) answers one deceptively simple question fast: are these two things in the same group? You start with a pile of separate elements, merge groups together over time, and keep asking "is x connected to y?" — and every one of those operations runs in nearly constant time.
Core idea. Represent each group as a tree and remember only one thing per element: who is my
parent? The root of a tree is the group's ID. union glues two trees together; find walks up to
the root. Two elements are connected exactly when they share the same root.
Intuition
Think of clubs on campus. Every student starts in a club of one — themselves. When two clubs decide to merge, you do not relabel every member; you just make one club's president report to the other's. To ask "are Ana and Ben in the same club?", each of them points up the chain of presidents until they reach the very top boss, and you check whether it is the same boss.
Two tricks keep the chains short. Union by rank: when merging, hang the shorter tree under the taller one so the result does not get tall. Path compression: every time you walk up to the boss, you re-point everyone you passed straight at the boss, so the next lookup is instant.
Walk through it
The canvas starts with six elements, 0 through 5, each its own little one-node tree. Step through the merges: union(0, 1) makes 0 the root and hangs 1 below it; union(2, 3) builds a second tree {2, 3}. Then union(1, 3) is the interesting one — neither 1 nor 3 is a root, so we climb to find their roots (0 and 2), and since the ranks tie, the whole {2, 3} tree slides under 0. Now {0, 1, 2, 3} is one set.
Finally we ask the connectivity question. find(0) is instant (it is the root). find(2) climbs one link to 0 — same root, so 0 and 2 are connected. The last step runs find(3), which has to climb two links (3 → 2 → 0); watch path compression re-point 3 straight at the root, flattening the tree for next time.
The code, line by line
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # compress
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra # attach smaller under larger
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1parent[x]is x's parent; a root is its own parent (parent[x] == x).rank[x]is a cheap upper bound on the tree's height.- Line 7-8 — path compression.
findrecurses up to the root, then on the way back assignsparent[x] = rootfor every node it touched. The chain collapses to depth 1. - Line 9 returns the root — the group's ID.
- Line 12-14 —
union. Find both roots. If they are already the same, the elements are already connected and there is nothing to do. - Line 15-17 — union by rank. Make sure
rais the taller (or equal) tree, then point the shorter rootrbatra. Hanging short under tall keeps the merged tree from growing. - Line 18-19. Only when two equal-rank trees merge does the height actually grow, so that is the one case where rank increments.
Complexity
| Case | Time | Notes |
|---|---|---|
| find / union (amortized) | O(α(n)) (moderate) | α = inverse Ackermann — under 5 for any real n |
| Build n singletons | O(n) (moderate) | init parent and rank arrays |
| Without compression + rank | O(n) (moderate) | a degenerate chain makes find linear |
O(n) (moderate)With both union by rank and path compression, any sequence of operations runs in O(α(n)) amortized per operation, where α is the inverse Ackermann function. It grows so slowly that for any input you will ever see it is below 5 — effectively constant. Use only one optimization (or neither) and a single find can degrade to O(n) on a long chain.
When to use / pitfalls
Reach for Union-Find whenever a problem is about grouping or connectivity that only ever merges (never splits): number of connected components, "are these two nodes connected," detecting a cycle while adding edges, or Kruskal's minimum spanning tree (union an edge only if its endpoints are in different sets). If you find yourself wanting to repeatedly ask "same group?", it is almost certainly DSU.
Two classic mistakes. First, comparing parents instead of roots — parent[a] == parent[b] is
not the same as find(a) == find(b); always call find. Second, plain DSU only handles merging; it
cannot efficiently split a set back apart, so do not reach for it when groups need to break up.
Practice
After union(0,1), union(2,3), and union(1,3), what does find(3) return — and how many parent links does it follow before path compression kicks in?
1. How do you decide whether two elements are in the same set?
2. What does union by rank accomplish?
3. What does path compression do during a find?
4. Why is amortized find/union effectively constant time?