15 — Union-Find (Disjoint Set Union)

What it is and what it's for

Union-Find answers one question extremely well:

"Are these two elements in the same group, given a stream of merges?"

Both operations run in near-constant time:

• find(x) — which group is x in?
• union(x, y) — merge the two groups containing x and y.

Why not just use DFS?

DFS answers connectivity too. The difference is when the edges arrive.

If the graph is fixed, one DFS pass labels every component: O(V + E), done.

But if edges arrive one at a time and you must answer "connected?" after each, DFS must re-run from scratch every time — O(E × (V + E)). Union-Find absorbs each new edge in O(α(n)) and always has the answer ready.

How it works

Each group is stored as a tree, and the root of the tree is the group's name. To ask "same group?", walk each element up to its root and compare.

Initially every element is its own root:
   0    1    2    3          parent = [0, 1, 2, 3]

After union(0, 1):
   0    2    3               parent = [0, 0, 2, 3]
   │
   1

After union(2, 3) and union(0, 2):
      0                      parent = [0, 0, 0, 2]
     / \
    1   2
        │
        3

The danger is that trees can grow tall and deep, making find slow. Two optimizations keep them flat.

The implementation to memorize

class DSU {
    private final int[] parent;
    private final int[] size;
    private int components;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;                       // every node starts alone
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        while (parent[x] != x) {              // walk up until we hit the root
            parent[x] = parent[parent[x]];    // PATH HALVING: point at the grandparent
            x = parent[x];
        }
        return x;
    }

    /** Returns false if x and y were ALREADY connected (i.e. this edge closes a cycle). */
    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;

        if (size[rx] < size[ry]) { int t = rx; rx = ry; ry = t; }   // UNION BY SIZE
        parent[ry] = rx;                      // attach the smaller tree under the larger
        size[rx] += size[ry];
        components--;
        return true;
    }

    boolean connected(int x, int y) { return find(x) == find(y); }
    int count() { return components; }
    int sizeOf(int x) { return size[find(x)]; }
}

The four design points, each load-bearing

1. parent[i] = i initially. Every element is its own root — n groups of one.

2. Path compression (here, "path halving").

parent[x] = parent[parent[x]];    // re-point x at its grandparent as we pass

Every find flattens the path it walks. The next find on those elements is faster. The recursive alternative compresses fully:

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

Path halving is one line, needs no recursion (no stack-overflow risk), and gives the same amortized bound. Prefer it.

3. Union by size. Always attach the smaller tree under the larger root. Attaching arbitrarily could build a long chain; attaching small-under-large keeps depth logarithmic. ("Union by rank" is the same idea using approximate height instead of size.)

Both optimizations are needed. With neither, worst case is O(n) per operation. With one, O(log n). With both, effectively O(1).

4. union returns a boolean. This is the part people miss, and it's what makes several problems one-liners:

• false means "already connected" → this edge creates a cycle.
• true means "merged two distinct groups" → the component count dropped.

Complexity

O(α(n)) amortized per operation, where α is the inverse Ackermann function — a function that grows so slowly it's at most 4 for any input that fits in the observable universe.

Say: "effectively constant, formally O(α(n))." Claiming plain O(1) invites a correction; knowing the real bound and its practical meaning reads much better.

Pattern 1 — count connected components

DSU dsu = new DSU(n);
for (int[] e : edges) dsu.union(e[0], e[1]);
return dsu.count();

Three lines. Every successful union merges two groups into one, so the count decreases by exactly one — which union already tracks.

Compare with the DFS version: build an adjacency list, allocate a visited array, loop over all nodes, run DFS from each unvisited one, count the launches. Both are correct; this is shorter and extends better.

Pattern 2 — cycle detection / first redundant edge

Redundant Connection: a tree had one extra edge added. Find it.

An edge whose endpoints already share a root must close a cycle — there was already a path between them, and this edge adds a second.

DSU dsu = new DSU(n + 1);                     // nodes are 1-indexed in this problem
for (int[] e : edges) {
    if (!dsu.union(e[0], e[1])) return e;     // union FAILED => already connected => cycle
}
return new int[0];

Trace: edges = [[1,2],[1,3],[2,3]]

Because edges are processed in input order, the first failure is the answer the problem asks for.

Watch the indexing. Problems labelling nodes 1..n need new DSU(n + 1) so index n is valid. Forgetting is an off-by-one that only surfaces on the last test case.

Pattern 3 — validating a tree

if (edges.length != n - 1) return false;      // O(1) rejection
DSU dsu = new DSU(n);
for (int[] e : edges) {
    if (!dsu.union(e[0], e[1])) return false; // a cycle
}
return true;

The argument: a tree on n nodes has exactly n − 1 edges.

• Fewer than n − 1 → must be disconnected (not enough edges to link everything).
• More than n − 1 → must contain a cycle.

So once the count check passes, proving "acyclic" is sufficient to conclude "connected" — you get the second property free. Stating that reasoning is worth more than the code.

Pattern 4 — Kruskal's minimum spanning tree

The goal: connect all nodes with minimum total edge weight.

The greedy rule: sort edges cheapest first, and take each one that connects two currently-separate groups. Skip any edge whose endpoints are already connected — it would only add a cycle without improving connectivity.

Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));   // {u, v, weight}

DSU dsu = new DSU(n);
int total = 0, used = 0;
for (int[] e : edges) {
    if (dsu.union(e[0], e[1])) {              // succeeded => this edge is useful
        total += e[2];
        if (++used == n - 1) break;           // a spanning tree needs exactly n-1 edges
    }
}
return total;

union's boolean return is precisely Kruskal's "does this edge create a cycle?" test. That's why DSU and Kruskal are inseparable.

The early break avoids scanning remaining edges once the tree is complete.

See 18 for Prim's, which is usually better on dense graphs.

Pattern 5 — non-integer elements

DSU indexes by int. For strings, coordinates, or objects, map them to integers first:

Map<String, Integer> id = new HashMap<>();
int nextId = 0;
for (String s : items) id.putIfAbsent(s, nextId++);
DSU dsu = new DSU(id.size());
// then union(id.get(a), id.get(b))

For grid cells, flatten the coordinate:

int index = r * cols + c;

Same arithmetic as the flattened matrix binary search (10).

Union-Find vs. DFS/BFS

DSU cannot undo

There is no efficient "un-merge". Once two groups combine, splitting them requires rebuilding.

The standard workaround: if a problem deletes edges over time, process the events in reverse — deletions become insertions, which DSU handles fine. Knowing this limitation and its fix is a genuine senior-level distinction.

Complexity summary

Recognition checklist

Reach for union-find when you see:

• "Connected", "components", "groups", "provinces", "friend circles"
• "Redundant" / "the edge that creates a cycle"
• "Is this a valid tree"
• Minimum spanning tree with a sparse edge list
• Merging equivalence classes — accounts, emails, equivalent variables
• Edges or queries that arrive over time

If the problem also asks for a distance or a path, union-find alone is insufficient — pair it with BFS, or reach for Dijkstra instead.