Union-Find (Disjoint Set)
The problem
Some problems repeatedly need to answer 'are these two items in the same group' and 'merge these two groups into one,' as groups keep merging over time — recomputing group membership from scratch after every merge is far too slow for problems with many merges.
Why now
Arrays and lists already gave fast indexed storage; union-find is a deliberately narrow structure built on top of it, answering only two questions (same group? merge groups) as cheaply as possible instead of supporting general-purpose queries a more powerful structure would need to pay for.
Mental model
Union-find represents each group as a tree where every node points toward a representative root, and 'same group' is just 'do these two nodes point to the same root.' Two optimizations — path compression (flatten the tree on every lookup) and union by rank (attach the smaller tree under the larger) — together make both operations run in nearly constant time, amortized over many calls.
Requires
- Arrays & ListsProgramming Fundamentals
Union-find's parent-pointer structure is almost always implemented as a simple array where index i's value is its parent; you need array indexing fluency for that compact representation to be legible.
Helps
- Complexity Analysis in PracticeComputer Science Fundamentals
Union-find's headline result — near-O(1) amortized operations with path compression and union by rank — is a genuinely surprising complexity claim that's worth being able to evaluate, not just accept, once you're already comfortable analyzing amortized cost.
Unlocks
Used in
- Kruskal's minimum spanning tree algorithm, using union-find to detect cycles cheaply
- Detecting cycles in an undirected graph without a full traversal
- Network connectivity queries ('are these two computers on the same network')
- Image processing — connected-component labeling
Projects
- Implement union-find with both path compression and union by rank, then use it to detect whether adding a given edge to a graph would create a cycle
- Use union-find to implement Kruskal's algorithm and compute a minimum spanning tree
Examples
- Adding an edge between two nodes that union-find reports are already in the same set means that edge would create a cycle — checked in nearly O(1), no traversal needed
- Without path compression, repeated finds can degrade to O(n) per call; with it, the tree flattens over time and finds approach O(1)
Resources
- Union-Find — MIT 6.006course
Mastery checklist
- I can implement union-find with path compression and union by rank
- I can use union-find to detect a cycle in an undirected graph
- I can explain why path compression and union by rank together give near-constant amortized time
- I can identify a problem that calls for union-find rather than a full graph traversal