Every club has a president: to know if two people are in the same club, ask who their presidents are; to merge clubs, one president reports to the other.
Clues that point here
→ "Are these connected?" asked many times
→ Number of connected components as edges are added
→ Detect a cycle in an undirected graph
→ Group accounts or equations
Not this pattern when
✕ You need the actual path between nodes (BFS/DFS)
✕ Edges are removed (DSU only merges)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Union-Find · template
int[] parent, rank;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // already together
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}