Released · improving
Algorithm
Union-find (disjoint set union) keeps elements in non-overlapping groups and can merge groups or check whether two elements share one in nearly constant time.
Union-find, also called the disjoint-set data structure, keeps a collection of elements split into non-overlapping sets. It offers just two operations: find returns the representative of the set an element belongs to, and union merges the sets of two elements. Each set is stored as a tree of parent pointers, and the root of the tree is the set's representative.
When connections only ever get added and you keep asking "are these two connected?", union-find is far faster than searching the graph each time. With path compression and union by rank or size together, the amortized cost per operation drops to the inverse Ackermann function α(n), which never exceeds 4 for any realistic input. It is the standard tool behind Kruskal's minimum spanning tree, cycle detection, connected components and grouping problems such as merging accounts, and it is a frequent coding interview topic.
Start by implementing find and union over a single parent array, and trace by hand how a tree degrades into a chain without optimizations. Then add union by size and path compression one at a time and watch how tree depth changes. Finally, solve connected-component, cycle-detection and Kruskal problems to get used to relying on union's return value.
find follows parent links up to the root (the representative), and union hangs one root under the other to merge two sets.
find re-attaches the nodes it visits directly to the root, flattening the tree so later calls are faster.
Hanging the smaller tree under the larger keeps every tree's height at most log n.
With both optimizations, m operations take O(m α(n)) time, and the inverse Ackermann function α(n) is at most 4 in practice.
The DSU class stores the sets in two arrays, parent and size. find walks up the parent links and uses path halving, linking each node to its grandparent, to keep trees flat. union hangs the smaller set under the larger one and returns False when both elements are already in the same set. The example merges six elements into three groups, then prints membership checks and the number of sets.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pySix chapters that take you from installation to the core ideas of Union-find.
Ask questions, share experience and trade opinions about Union-find.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.