← All patterns
Union-Find (Disjoint Set)
A data structure that tracks a partition of elements into disjoint sets, supporting near-O(1) union and find via path compression + union by rank.
When to use it
- Dynamic connectivity questions: 'are these two nodes connected', counting connected components, detecting cycles while building a graph incrementally (e.g. Kruskal's MST).
Signals in the problem statement
- Repeated 'connect A and B' operations interleaved with 'are A and B connected' queries.
Common pitfalls
- Forgetting path compression/union by rank, degrading to O(n) per operation in the worst case.
Practice Problems
No problems tagged yet for this pattern.