Level 4 · Graph AlgorithmsBUILD YOUR INTUITION
Union Find
Represent disjoint components by rooted parent forests and merge components by linking their roots.
THE MENTAL MODELWhen should this come to mind?
Represent disjoint components by rooted parent forests and merge components by linking their roots.
Incremental undirected connectivityCount componentsRedundant undirected edges What makes it work
Find roots before merging. Union by size keeps tree height logarithmic; path compression can further speed up repeated finds.
When to choose something else
Union find does not recover paths or handle arbitrary edge deletions. Directed reachability needs another algorithm.
See the pattern in action
Change the input. Follow the state. Make it yours.