TutorialMar 10, 2026 · 7 min
Union-Find: the data structure you forgot you needed
Five problems where Union-Find turns an O(N²) brute force into something that runs in milliseconds.
Disjoint-Set Union (DSU), commonly called Union-Find, is the unsung hero of competitive programming. It answers two questions in near-constant amortised time: 'are A and B connected?' and 'merge their components.'
Five problems it cracks
- Kruskal's MST in O(E log E)
- Connected components in a dynamic graph
- Cycle detection in an undirected graph
- Offline LCA queries (Tarjan)
- Number of islands when cells are added one at a time