Union-Find
Why it exists
Problem: In dynamic undirected networks where edges are continually added, repeatedly running O(V+E) BFS or DFS to check if two nodes are in the same component becomes an unsustainable bottleneck.
Better idea: Instead of full graph traversals, model connected components as a forest of trees. A Disjoint-Set Union (DSU) structure can link trees and trace roots in near-constant time to answer connectivity queries.
Mental model
Every node starts in its own isolated component. When you add an edge, you find the 'leader' (root) of both nodes. If the leaders are different, you merge the components by making one leader follow the other.
Union-Find bypasses literal graph traversal. It maintains a parent array where each node points to a parent. Finding a node's component means walking up parent pointers until you hit a node that points to itself—the root. A 'Union' operation links two roots. To keep things fast, we always attach the smaller tree under the larger root (Union by Rank) and flatten the path to the root during every search (Path Compression).
Repeated decision: At each step: are these two nodes already in the same set — i.e. do they share a root?
Explanation
Union-Find (or Disjoint-Set Union, DSU) elegantly tracks connected components in an **undirected** graph without tracking full paths. It stores just one array, `parent`, where `parent[i]` is the parent of node `i`. The root of a tree represents the entire set's ID.
### The Operations
1. **Find(x)**: Walk up `parent` pointers from `x` until you reach a node `r` where `parent[r] == r`. This is the root.
2. **Union(x, y)**: Find the root of `x` and the root of `y`. If they differ, update one's `parent` to point to the other.
### The Optimizations
Without optimization, Union operations could link trees linearly into a linked list, degrading `Find` to O(n). We apply two tricks:
- **Union by Rank/Size**: Track the size of each tree. Always hang the smaller/shallower tree under the root of the larger tree.
- **Path Compression**: During `Find(x)`, as you walk up to the root, update every node along the path to point *directly* to the root. This flattens the tree for future queries.
Together, these make the operations run in **effectively constant** amortized time (inverse-Ackermann). This is the key insight from amortized analysis: individual operations might be slow, but they guarantee future operations are fast.
### Hand-Trace
Consider 6 nodes (0 to 5) initially isolated. `parent = [0, 1, 2, 3, 4, 5]`.
- **Union(0, 1)**: `Find(0)` is 0, `Find(1)` is 1. Make 1 point to 0. `parent = [0, 0, 2, 3, 4, 5]`.
- **Union(1, 2)**: `Find(1)` traces to 0. `Find(2)` is 2. Make 2 point to 0. `parent = [0, 0, 0, 3, 4, 5]`.
- **Union(3, 4)**: `Find(3)` is 3, `Find(4)` is 4. Make 4 point to 3. `parent = [0, 0, 0, 3, 3, 5]`.
- **Union(2, 4)**: `Find(2)` is 0, `Find(4)` is 3. We link root 3 to root 0. `parent = [0, 0, 0, 0, 3, 5]`.
- Next time we run `Find(4)`, it traces `4 -> 3 -> 0`. Path compression then updates `parent[4] = 0`.
Common mistakes
- Forgetting path compression: Implementing `Find` with a simple while loop without updating the pointers along the way loses the O(1) amortized guarantee.
- Union without Find: Linking the nodes directly (e.g., `parent[u] = v`) instead of linking their roots (`parent[Find(u)] = Find(v)`) creates broken, disconnected trees.
Recall questions
- What two optimizations give Union-Find its effectively constant time complexity?
- What does path compression do during a Find operation?
- How does Union-Find verify if two nodes are in the same component?
Questions & answers
How do you detect a cycle in an undirected graph using Union-Find?
Iterate over edges. For each edge (u, v), if Find(u) == Find(v), a cycle exists because they are already connected. Otherwise, Union(u, v).
Approach: Recognize that a cycle is formed when you add an edge between two nodes already in the same set.
What is the time complexity of Union-Find operations with both optimizations?
Effectively constant amortized time (inverse-Ackermann function), which is bounded for any realistic input size.
Approach: Always specify that the effectively constant bound is amortized over many operations, not guaranteed per single operation.
Continue learning
Previous: Graph representations
Previous: Amortized Analysis