Track connected components efficiently with path compression and union by rank.
Union-Find (Disjoint Set Union) efficiently tracks which elements belong to the same connected component. With path compression and union by rank, both find and union run in near O(1) amortized time (O(α(n)) — inverse Ackermann).
O(α(n)) ≈ O(1) amortized per operation
O(n)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
returns the root representative of a set
merges two sets by connecting their roots
on find, make all nodes point directly to root
attach smaller tree under larger tree to keep height low
if find(u) === find(v) before union, edge (u,v) creates a cycle
number of islands, redundant connections, MST (Kruskal)