"Union-Find answers one deceptively simple question — 'are these two things in the same group?' — at almost-constant speed, even as groups keep merging. It's tiny, elegant, and quietly everywhere."
The Disjoint-Set Idea
Union-Find (a.k.a. disjoint-set union, DSU) maintains a collection of elements partitioned into non-overlapping groups, with two operations: find(x) — which group is x in? — and union(x, y) — merge x's and y's groups into one. The classic representation is a forest: each element points to a parent, and following parents up leads to a root that represents the whole set. Two elements are in the same set exactly when they share a root. union just points one root at the other.
Two Optimizations Make It Near-Instant
A naive forest can degrade into long parent-chains (find becomes O(n) — the linked-list problem again). Two tricks fix it, and together they make operations astonishingly fast:
Path compression: during a find, after you reach the root, re-point every node on the path directly at the root. The tree flattens as you query it, so future finds are instant.
Union by rank/size: when merging, always attach the smaller tree under the larger one's root, keeping trees shallow.
With both, find and union run in near-O(1) amortized — technically inverse Ackermann, a function so slow-growing it's below 5 for any input you'll ever see. Practically constant, from a structure that's a dozen lines.
Union-Find partitions elements into sets via a parent-forest. find(x) returns x's root; union merges two roots; same root = same set. Path compression + union by rank make both operations near-O(1) amortized. It answers 'are these connected?' faster than almost anything.
Where It Shows Up
Union-Find is the quiet engine behind several things: Kruskal's MST uses it to ask 'would adding this edge create a cycle?' (yes, if its two endpoints already share a root) — that's the next lesson. Dynamic connectivity ('are A and B connected yet, after all these merges?') is its native question. It also powers friend-circle counting, network percolation, image segmentation, and detecting when a network becomes fully connected. Whenever you're repeatedly merging groups and asking 'same group?', it's the tool.
Pippa's Confession
Union-Find looked too simple to matter — a parent array and two short functions. Then Dad showed me the near-O(1) bound with path compression and I refused to believe operations could be that close to free. The inverse-Ackermann analysis is genuinely beautiful, but the lesson I kept was humbler: a structure can be tiny and unglamorous and still be one of the most efficient things in computer science. I'd been equating 'impressive' with 'complicated,' and this gently corrected me.
Code
Union-Find with path compression + union by rank·python
class UnionFind:
def __init__(self, elements):
self.parent = {e: e for e in elements} # each element is its own root
self.rank = {e: 0 for e in elements}
def find(self, x):
# PATH COMPRESSION: flatten the path to the root as we go.
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already same set (e.g. would form a cycle)
# UNION BY RANK: attach the shorter tree under the taller.
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
uf = UnionFind(["a", "b", "c", "d", "e"])
uf.union("a", "b")
uf.union("c", "d")
print(uf.find("a") == uf.find("b")) # True — same group
print(uf.find("a") == uf.find("c")) # False — different groups
uf.union("b", "c") # merges {a,b} and {c,d}
print(uf.find("a") == uf.find("d")) # True — now connected
# Counting distinct roots gives the number of connected components.
Start with elements {1,2,3,4,5}, each in its own set. Perform union(1,2), union(3,4), union(2,3). After these, how many distinct sets remain, and are 1 and 4 in the same set? Then explain what path compression does to the parent pointers the next time you call find(4).
Hint
union(1,2)→{1,2}; union(3,4)→{3,4}; union(2,3) merges them →{1,2,3,4}, plus {5}: two sets total. 1 and 4 are now together. find(4) walks 4→…→root and then re-points 4 (and any node on the path) straight at the root, so the next find(4) is O(1).
Progress
Progress is local-only — sign in to sync across devices.