Union-Find tracks connected components efficiently. Core Operations:
- Find: Return root with path compression
- Union: Merge by rank/size
Optimizations:
- Path compression: Flatten tree during find
- Union by rank: Attach smaller to larger
Applications:
- Connected components counting
- Cycle detection in graphs
- Kruskal's MST algorithm
- Dynamic connectivity queries
Complexity: amortized per operation where is inverse Ackermann. Space: for parent and rank arrays.