Tracks a partition of elements into disjoint sets: find(x) gets the set's representative, union(x,y) merges two sets. Path compression plus union by rank/size gets near-O(1) amortized operations, which is what makes connectivity and cycle-detection queries fast.
Sub-patterns
- A — Basic Connectivity. Are two nodes in the same set?
- B — Cycle Detection. In an undirected graph, an edge between two already-connected nodes means a cycle.
- C — Kruskal's MST. Sort edges, union if they don't already connect the same set (also relevant to Minimum Spanning Tree).
- D — Dynamic Connectivity. Answering connectivity queries as edges are added over time.
Practice set (8)
- Medium — Number of Provinces, Redundant Connection, Accounts Merge, Graph Valid Tree (Premium), Smallest String With Swaps, Most Stones Removed with Same Row or Column
- Hard — Number of Islands II (Premium), Swim in Rising Water (also relevant to Shortest Path)
Pending
Basic Connectivity
Are two nodes in the same set? The core find/union query.
Pending
Cycle Detection
In an undirected graph, an edge between two already-connected nodes signals a cycle.
Pending
Kruskal's MST
Sort edges by weight, union two nodes only if they don't already share a set — the edge-sorted MST algorithm.
Pending
Dynamic Connectivity
Answer connectivity queries as edges are added over time, without rebuilding from scratch.
Notes from readers
Comments — via GitHub