Contrast with Day 4's component counting: BFS/DFS needs the whole graph up front and recomputes on change. Union-Find handles a stream of unions with near-constant cost per operation — which is why it underpins Kruskal's MST (Day 13) and countless "merge accounts / detect cycle" problems.
Represent each set as a rooted tree; the root is the set's canonical representative. A single array parent[] encodes the whole forest: parent[x] is x's parent, and a root points to itself.
Why "basic" is slow. With naive union (always attach a's root under b's), you can build a degenerate chain of length n, making find take O(n). That's the motivation for tomorrow's two optimizations.
This is a classic equivalence-relation data structure: reflexive (x~x), symmetric (union is order-independent for connectivity), transitive (merging chains).
| Operation | Time (naive) | Why |
|---|---|---|
| find | O(n) worst | Degenerate chain possible without balancing. |
| union | O(n) worst | Dominated by two finds. |
| space | O(n) | Single parent[] array. |
Deliberately un-optimized so the structure is clear.
/** Basic Union-Find — no rank, no path compression (yet). */
public class UnionFind {
private final int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i; // each its own root
}
/** Walk up to the root — the set's representative. */
public int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
/** Merge the two sets; returns false if already together. */
public boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // same set → nothing to do
parent[ra] = rb; // naive: attach ra under rb
return true;
}
public boolean connected(int a, int b) { return find(a) == find(b); }
}
parent[a] = b instead of parent[find(a)] = find(b) corrupts the forest. Always union the roots.The tell is merging groups + connectivity queries, especially as relationships arrive incrementally. Even in "basic" form the pattern recognition is the same:
| Disguise / phrasing | What's really asked | Twist to handle |
|---|---|---|
| "Provinces / friend circles" (static) | Count components | Union all edges, count distinct roots |
| "Equations a==b, a!=b consistent?" | Equivalence + contradiction check | Union all '==' first, then verify '!=' pairs differ |
| "Similar strings / groups by relation" | Grouping by transitive relation | Union when relation holds; group by root |
| "Are u and v connected?" (interleaved) | Dynamic connectivity | Keep one DSU alive; don't rebuild |
| "Two-set / bipartite via DSU" | Enemy-of-enemy grouping | Extended DSU with 2n nodes (self / opposite) |