Connectivity
Near-constant-time connectivity with path compression + union by rank.
The idea
A disjoint-set union (DSU) maintains a partition of elements and answers 'are these connected?' plus 'merge these two groups' in almost O(1) amortised, thanks to path compression and union by rank.
This visualization plays a sequence of unions: each one finds the two roots (compressing the paths it walks) and links the shorter tree under the taller — watch separate components fuse into one.
Merging friend circles: introduce two people and their entire social groups become one, all pointing to a shared representative.
When to reach for it
- Dynamic connectivity queries.
- Cycle detection while adding edges.
- Kruskal's minimum spanning tree.
Language-independent template
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # compress
x = parent[x]
return x
def union(a, b): parent[find(a)] = find(b)Complexity — time O(α(n)) per op, space O(n).
Common mistakes
- Skipping path compression (slow finds).
- Not using union by rank/size.
- Treating directed edges as undirected.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Determine whether two vertices belong to one connected component.
Find the edge that creates a cycle in an almost-tree.
Count paths whose endpoints share the path's maximum value.