Coding Prep
Union-Find
A disjoint set data structure that tracks connected components in near-O(1) per operation - path compression and union by rank combine to give O(alpha(n)) amortized, faster than BFS/DFS for dynamic connectivity.
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.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size)) # each node starts as its own parent
self.rank = [0] * sizeTwo 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.
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).
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.Canonical examples
Number of provinces (connected components)
Given an adjacency matrix, count the number of connected groups. Initialize n components; for each edge, call union - if it returns True (a merge happened), decrement the component count. The final count is the answer.
Redundant connection (cycle detection)
Given edges added one by one to a graph, find the first edge that creates a cycle. Process edges in order; the first union call that returns False (the two nodes are already connected) identifies the redundant edge.
a->b from b->a.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.
Practice problems
- Number of Provinces - Connected components via adjacency matrix.
- Redundant Connection - First cycle-creating edge.
- Number of Connected Components in an Undirected Graph - Component count with edge list input.
- Accounts Merge - Union accounts sharing an email; then group by root.
- Satisfiability of Equality Equations - Union equal pairs, check inequality pairs for conflict.
Done reading? Mark it so it sticks in your dashboard.