What is Union-Find?
Union-Find stores a collection of separate groups and supports two operations: find which group an item belongs to, and merge two groups. It is also called Disjoint Set Union, or DSU.
You need arrays, trees, and graph components. The short version is: give each component one representative root and compare roots to answer connectivity questions.
The Core Idea: Compare Representatives
In LC 684: Redundant Connection, edges [1,2] and [1,3] first place nodes 1, 2, and 3 in one component.
When edge [2,3] arrives, both endpoints already have the same root.
What does that tell us? A path between 2 and 3 already exists, so adding another edge creates a cycle.
It is like checking family membership through a household representative. Two people belong to the same household when following their records leads to the same representative.
How One Edge Is Processed
The Rule You Keep True
Following parent links from any node must end at the unique representative root of that node's component. Two nodes are connected exactly when their roots are equal.
Two optimizations protect performance:
- Path compression points visited nodes closer to the root during find.
- Union by rank or size attaches the shallower or smaller tree below the other root.
Accounts Merge is the one that usually trips us up. The union operations are straightforward, but the final answer still needs every email grouped by root and sorted for output. Union-Find solves membership, not result formatting.
Picking the Right Shape
From Rule to Code
- Initialize each node as its own parent with rank or size metadata.
- Implement
findby following parents to a root and compressing the path. - For each edge, find both roots.
- If the roots differ, attach one root to the other according to rank or size.
- If the roots match, handle the already-connected or cycle case requested by the problem.
With path compression and union by rank, each operation takes amortized O(α(n)) time, which is effectively constant for practical inputs.
When to use it
- •Edges arrive and you need to know which nodes belong to the same component.
- •The problem asks whether adding an edge creates a cycle.
- •Groups repeatedly merge but do not need to split.
- •Connectivity queries must be answered faster than traversing the graph each time.
How to identify it
- •The input is a list of pairwise connections.
- •The prompt mentions components, provinces, redundant edges, accounts, or connectivity.
- •Operations repeatedly ask whether two items are already connected.
- •Only group membership matters, not the exact path between nodes.
Key insights
- →Each set has one representative root.
- →`find(x)` follows parent links until it reaches the root of `x`'s set.
- →`union(a, b)` links two different roots, not arbitrary member nodes.
- →Path compression makes later finds point closer to the root.
- →Union by rank or size keeps the parent trees shallow.
Common mistakes
- 01Comparing immediate parents instead of comparing roots returned by `find`.
- 02Joining arbitrary nodes without finding their roots first.
- 03Forgetting to initialize every node as its own parent.
- 04Decreasing the component count when an edge connects nodes already in the same set.
- 05Using Union-Find when the actual path, distance, or removal of edges matters.