Union-Find
Loading visualizer…
Initialize
0
01
12
23
34
45
56
67
70
1
2
3
4
5
6
7
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Union-Find
Loading visualizer…
Initialize
Disjoint Set Union (DSU) — track which elements are in the same connected component. Watch how path compression and union by rank push the cost to near-constant.
Store a component ID per element. find() is O(1) — just return id[x]. union() is O(n) — scan the entire array and relabel.
O(n) unionO(n)Flat ArrayStore a parent pointer per element. union() is O(1) — just repoint one root. find() follows parent links to the root — O(n) worst case (tall trees).
O(n) findO(n)Tree PointersAfter find(x), point every node on the path directly to the root. Trees flatten dramatically. Amortised cost approaches O(α(n)) — nearly constant.
O(α(n)) amort.O(n)Flatten on FindAlways attach the shorter tree under the taller one. Rank tracks tree height. Combined with path compression this is the optimal Union-Find.
O(α(n)) amort.O(n)Height HeuristicWith path compression + union by rank, each operation costs O(α(n)) — the inverse Ackermann function. For all practical n, α(n) ≤ 4. Effectively O(1) per operation.
Union-Find is the engine behind Kruskal's algorithm. It checks in O(α(n)) whether adding an edge creates a cycle — enabling an O(E log E) MST algorithm.
Track connected components as edges arrive. Union merges two components; find checks if two nodes are already connected. Used in network analysis, image segmentation, and compilers.