Union-Find (DSU) — definition.
Definition
A disjoint-set data structure supporting near-constant merge and find.
Complexity
Amortized O(α(n)) per op with path compression + union by rank.
When to use it
- Connectivity queries on a graph that only grows.
- Counting connected components.
- Detecting cycles as edges arrive (e.g., Kruskal's MST).
Representative scenarios
- Friend-Circle Counter — count connected people clusters.
- Extra Cable Finder — detect redundant edges.
- LAN Mesh Audit — validate full connectivity after merges.
Related patterns
Read the full pattern page: Union-Find (DSU) — template, code, and drills.
Run the free diagnostic.
Ten-minute patterns quiz. No card. Personalized loop starts on the other side.