Union Find
Track connected components efficiently with union and find operations, using path compression and rank optimization.
- • Connected components
- • Cycle detection in undirected graphs
- • Kruskal's MST
- • Dynamic connectivity
- • Need shortest paths
- • Directed graphs (use other methods)
- • Need to split components
- • Forgetting path compression
- • Not using union by rank
- • Confusing with BFS/DFS connectivity
Key Invariant
Find with path compression + union by rank gives nearly O(1) amortized operations