Advanced Structures
Union-Find (disjoint set)
Track connected components in near-constant time
You are carving a maze, and each time you knock out a wall you must ask: were these two cells already connected? Or you are clustering pixels, or friends, or network nodes, and you keep asking the same two things - are these two items in the same group? and merge their two groups into one. A plain array or hash set answers the first slowly and the second not at all. Union-Find - the disjoint-set data structure - answers both in effectively constant time, using nothing but a single array of parent pointers plus two tiny tricks.
Groups are trees; the root is the name
Partition elements into disjoint groups - every element lives in exactly one group. Represent each group as a tree of parent pointers: each element points at its parent, and the one element that points at itself is the root. The root is the group's identity - its representative name. So the connectivity question becomes almost trivial: two elements are in the same group precisely when walking up from each lands on the same root. We never store the groups explicitly; we just store one number per element, .
Find and union
Everything reduces to two operations on that parent array. Find climbs from an element to its root; union hooks the root of one tree beneath the root of another. Naively, both are as cheap - or as expensive - as the tree is tall.
The two operations
find() follows parent pointers until it reaches a self-pointing node:
union() computes and ; if they differ, it sets , fusing the two trees. And connected() is just . The whole cost of every operation is the cost of a find, which is the tree's height. Chain the elements into a single tall stick - union 1 under 0, 2 under 1, 3 under 2 - and find degrades to . The two optimizations below exist to stop that stick from ever forming.
Keeping the trees flat
Two independent tricks, each a few lines, together crush the height to near nothing.
Union by rank (or by size): never attach the taller tree under the shorter one. Keep a per root - a running upper bound on its height - and always hang the shorter tree beneath the taller root. A tree's height only grows when two equal-rank trees merge, so height stays on its own.
Path compression: a find already visited every node between and the root - so on the way back, repoint each of them directly at the root. The next find on any of them costs one hop. One traversal pays to flatten the whole path it touched. Toggle it on in the demo and watch a five-deep chain collapse into a flat fan on a single click.
Play with the forest
Ten elements, each starting as its own root. Pick a tool, then click. In Union mode click two elements to merge their trees; in Find mode click one and watch it climb to its root - with path compression on, the whole path flattens as it goes. In Connected? mode click two elements to test if they share a root. The cost meter counts the pointer hops each find takes; do a deep find twice and watch the second one drop to a single hop.
Union mode: click one element, then a second, to merge their sets under a single root.
Near-constant: inverse Ackermann
Union by rank alone gives per operation. Path compression alone gives amortized . But used together, Tarjan (1975) proved that any sequence of find/union operations on elements runs in
Here is the inverse Ackermann function - it grows so slowly that for any up to a number vastly larger than the count of atoms in the universe. So each operation is amortized near-constant. It is famously not exactly : no data structure supporting these operations can be, but in practice it is indistinguishable from it.
The code
The entire structure is one parent array, one rank array, and two short methods. Note the two-pass find: first walk up to locate the root, then walk up again repointing each node straight at it.
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # every element is its own root
self.rank = [0] * n # upper bound on each tree's height
def find(self, x): # return root, compressing the path
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # path compression: point straight at root
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b): # merge the sets of a and b
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already together - an edge here makes a cycle
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra # hang the shorter tree under the taller root
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1 # equal ranks: the winner grows by one
return True
def connected(self, a, b):
return self.find(a) == self.find(b)Check yourself
During a find, what does path compression change?
With union by rank and path compression, the amortized cost per operation is:
Recall: name the two optimizations that make Union-Find near-constant, and what each one does.
Recall the two tricks. Try to state it, then check.
Lock it in
- Union-Find represents disjoint groups as trees of parent pointers; the root is the group's identity, so two elements are connected exactly when they share a root.
- Everything reduces to two operations on one parent array: find climbs to the root, union hooks one root under another. Naive cost is the tree's height, up to .
- Two tricks flatten the trees: union by rank hangs the shorter tree under the taller (height ), and path compression repoints every visited node straight at the root.
- Together they give amortized , where the inverse Ackermann for any you could store - near-constant, though provably not exactly .
Primary source
Ask your teacher