Foundations
Union-Find
Track which elements are connected. Near-O(1) per op with path compression and union by rank.
What is Union-Find?
Union-Find (Disjoint Set Union, DSU) tracks a collection of elements partitioned into disjoint sets. Two operations define it: find(x) returns the representative (root) of x's set; union(x, y) merges the sets containing x and y into one.
Two optimizations are critical. Path compression: during find, point every node directly to the root so future finds are faster. Union by rank: always attach the shallower tree under the taller one to keep tree height bounded. Together they give O(alpha(n)) amortized per operation, where alpha is the inverse Ackermann function - effectively O(1) for any realistic input.
The core trade-off: Union-Find is faster than BFS/DFS for repeated connectivity queries on a dynamic graph where edges are added over time. BFS/DFS re-traverses the whole graph each time; Union-Find answers each query in near-O(1). But Union-Find only handles undirected graphs and cannot detect directed cycles.
Core operations
| Operation | Time (with optimizations) | Notes |
|---|---|---|
find(x) | O(alpha(n)) amortized | Path compression: flattens tree on every call |
union(x, y) | O(alpha(n)) amortized | Union by rank: attach smaller tree under larger |
connected(x, y) | O(alpha(n)) amortized | find(x) == find(y) |
| Build from n elements | O(n) | Initialize parent and rank arrays |
| Count components | O(1) | Maintain a component count, decrement on successful union |
Key patterns
Path compression in find
During find, recursively make every node on the path point directly to the root. After one traversal, subsequent calls for the same node jump straight to the root.
When to use - any time you call find, which is every operation: connectivity checks, merges, component counts. Without it, a chain of unions builds a tall tree and each find walks the whole height at O(n). Compression is what collapses that walk.
How it works - on the way back up from the recursive find, reassign every node you passed to point straight at the root. The tree flattens a little more on each call, so repeated lookups get cheaper over time. Paired with union by rank or size - always hanging the shorter tree under the taller one - the cost per operation amortizes to O(alpha(n)), where alpha is the inverse Ackermann function. That grows so slowly it is effectively a small constant for any input you will ever see, though it is not literally O(1) and is faster than the O(log n) you would get from union by rank alone.
Example: flatten a chain. After unions 0-1, 1-2, 2-3, 3-4 the parent map reads 0 -> 1 -> 2 -> 3 -> 4, so find(0) climbs 4 hops to reach root 4. A second pass then repoints 0, 1, 2, and 3 straight at the root, one per step. Every node on the path now reaches root 4 in a single hop - the visualizer below walks and compresses each link.
find is O(n) per call - a chain of unions without compression creates a linked list where every find traverses the full chain. Path compression flattens this over time, giving the amortized guarantee.Union by rank
Always attach the tree with lower rank (shallower) under the tree with higher rank (taller). If ranks are equal, attach either and increment the winner's rank by 1.
When to use - inside every union, whenever you are merging two sets and need to decide which root survives. The signal is the same one that sends you to Union-Find at all: dynamic connectivity, "are these in the same group?", repeated merging. Attach trees blindly and they grow into chains, dragging find back to O(n); rank is what stops that.
How it works - track an approximate height (rank) for each root and always hang the shorter tree under the taller one, so the merged tree is no deeper than its tallest input. Heights only tie up when two equal-rank trees meet, and then the survivor's rank ticks up by 1, which is why depth grows logarithmically at worst rather than linearly. On its own this bounds find at O(log n); combined with path compression the amortized cost drops to O(alpha(n)) - inverse Ackermann, effectively a constant for realistic inputs but not literally O(1).
Example: merge by height. Unions 0-1 and 2-3 tie at rank 0, so 1 lands under 0 and 3 under 2, each winner bumped to rank 1. 0-2 ties again at rank 1, 2 attaches under 0, and rank[0] hits 2. 4-5 builds a rank-1 tree, and the final 4-0 sees rank[0] = 2 beat rank[4] = 1, so 4 hangs under 0 - nothing ends up deeper than 2 hops from root 0, and the visualizer below shows the rank array growing.
union - returning True when a merge actually happened (roots were different) and False when they were already connected lets callers detect cycle formation: if union returns False, adding this edge creates a cycle.When to reach for Union-Find
- You need to dynamically merge groups as edges are added and repeatedly query connectivity.
- The problem asks to detect the first edge that creates a cycle in an undirected graph.
- You need to count connected components and that count changes as edges are added.
- The problem involves grouping elements by a transitive relation (accounts merge, similar strings).
- BFS/DFS would work but the graph is large and you need many connectivity queries - Union-Find amortizes the cost.
- The problem says minimum spanning tree - Kruskal's algorithm builds the MST by greedily adding edges via Union-Find.
Done reading? Mark it so it sticks in your dashboard.