When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Dynamic connectivity
- Redundant edge
- Component count
When another approach fits better
- Edges are deleted online
- You need shortest paths, traversal order, or the actual connecting route
How it works#
Run DFS/BFS after every added edge to rediscover connectivity.
Initialize every item as its own parent.
Compress paths during find.
Attach the smaller/rank-lower root under the larger/rank-higher root and update metadata only there.
InvariantEach component has one representative root; find returns that root, and union changes only roots while preserving membership.
Example and template#
Redundant Connection
Detect the first edge whose endpoints are already connected.
Open the full problem brief- Before
0←1 and 2←3Two components have representatives 0 and 2.
- Union 1,3
0←1,2,3Find roots first; then one root attaches under the other.
find(x):
if parent[x] != x: parent[x] = find(parent[x])
return parent[x]
union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return false
attach smaller root under larger root
return true- Time
- O(α(n)) amortized per operation
- Space
- O(n)
- Assumptions
- Path compression and union by size/rank are both used; α is inverse Ackermann.
Pitfalls#
Common wrong approaches
Union must connect representatives or it can corrupt the forest.
Size/rank belongs only to roots and changes under a specific attachment rule.
Edge cases
- Union within one component
- Unknown item initialization
- One element
- Component count updates
Interview narration
- “I only need component identity, not an explicit route.”
- “Find returns and compresses the representative.”
- “Unioning equal representatives reveals a redundant connection.”
Practice#
Redundant Connection
Detect the first edge whose endpoints are already connected.
Practice this problemAs cables are added, report after each addition how many isolated networks remain.
Reveal the pattern decision
Use union-find and decrement the component count only when two representatives differ.
Transfer problem
Accounts share email identifiers; merge records connected by any email.
Checkpoint: Choose stable node IDs and perform unions through each shared identifier before grouping by root.
Follow-up variations
- Return component sizes
- Explain why arbitrary online deletions need a different data structure or offline strategy
Error-log prompts
- Did union operate on roots?
- Was rank or size updated on the surviving root only?