{ } GraphAdvanced interactive
Union-Find (DSU)
Near-constant merge & connectivity checks.
union_find
8 sets
Each element starts in its own set. Union merges; find returns the root.
arrows point to parent · color = connected component
How it works
Disjoint-Set Union tracks elements partitioned into groups, answering 'are these two connected?' and 'merge these groups' in almost O(1) using path compression and union by rank. It's the heart of Kruskal's MST and cycle detection.
Mental models
- Path compression flattens trees on every find.
- Union by rank attaches the smaller tree under the larger.
Complexity
- Find
- O(α(n))inverse Ackermann ≈ 1
- Union
- O(α(n))
- Space
- O(n)
Reach for it when
- Kruskal's MST
- Connected components
- Cycle detection