Union-Find (Disjoint Set Union)

Union-Find (Disjoint Set Union)

A Union-Find (DSU) structure maintains a partition of n elements into disjoint sets by storing, for each element, a pointer toward a representative (root) of its set; find(x) walks parent pointers to the root, and union(x,y) links the two roots together — so two elements are in the same set exactly when their roots coincide, and merging sets costs only a pointer update rather than relabeling every member.

Recognize the pattern

• The problem repeatedly asks "are these two things connected / in the same group?" interleaved with "merge these two groups," and you never need to undo a merge.
• You are building a spanning structure incrementally and must detect a cycle cheaply — the textbook case is Kruskal's MST, and "count connected components while edges stream in."
• Offline connectivity: given a fixed batch of union operations, answer queries in any order without rebuilding a graph traversal each time.
• Problems literally named "number of islands," "accounts merge," "redundant connection," "friend circles," "smallest equivalent string."

Baseline vs. this algorithm

Naive baseline — graph traversal: model connectivity as an adjacency list and run BFS/DFS from a node whenever you need to answer "is x connected to y?" Each query costs O(V+E). If you instead try to maintain an explicit component-id array and merge two components by relabeling every node in one of them, a single merge costs O(size of the component being relabeled), which is O(n) in the worst case — and an adversarial sequence of n merges can cost O(n²) total.

Union-Find: represent each set as a small in-tree (parent pointers, not a full adjacency structure). find(x) costs O(height of x's tree). union(x,y) costs one find on each side plus O(1) to re-point a root. Two optimizations make the trees shallow:

• Union by rank/size: when merging, attach the root of the smaller tree under the root of the larger tree (by subtree size or by an upper-bound "rank"). This alone caps tree height at O(log n), since a node's depth only increases when its tree is the smaller one being absorbed, at least doubling that tree's size each time.
• Path compression: during find, re-point every node visited on the path directly to the root. This flattens the tree for all future queries through those nodes.

Used together, the amortized cost per operation is O(α(n)), where α is the inverse Ackermann function — for any n that fits in the physical universe, α(n) ≤ 4, so this is "practically constant."

Complexity, derived from first principles

Without either optimization: a chain can form (union always attaches root of x under root of y, y under z, ...), giving tree height O(n), so find is O(n) worst case.

With union by size alone (no compression): every time a node's depth increases by 1, it just moved from a tree of size s into a merged tree of size ≥ 2s (because we always attach the smaller side, so the tree it joined was at least as big as its own). A node can only be on the "smaller side" O(log n) times before the total number of elements n is exhausted, since size at least doubles from that node's perspective each time its depth grows. Hence height ≤ O(log n) and find is O(log n) worst case.

Adding path compression: a single find can still touch O(log n) nodes on a cold path, but every node it touches gets re-attached directly to the root — so the next find through any of them is O(1). This combined bound is Tarjan's classic amortized-analysis result (a potential-function / block argument over ranks): any sequence of m union/find operations on n elements costs O(m·α(n)) total, i.e., O(α(n)) amortized per operation — cited here rather than re-derived, since the full block argument is a page of its own, but the O(log n) case above is fully derived from first principles. Space is O(n): one parent slot and one rank/size slot per element — no adjacency list, no visited array.

Traced worked example

Elements 0..6, all start as singleton sets: parent[i] = i, size[i] = 1. Process unions in this order: union(0,1), union(1,2), union(3,4), union(5,6), union(2,3), find(6) with path compression.

Note element 4 sits at depth 2 (4→3→0). A subsequent find(4) would walk 4→3→0, then path-compression re-points parent[4] = 0 directly, so any later find(4) is O(1).

Java implementation

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

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        components = n;
    }

    // Path compression: point every visited node straight at the root.
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    // Union by size: attach smaller tree under larger tree's root.
    // Returns false if x and y were already in the same set (cycle detected).
    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; }
        parent[ry] = rx;
        size[rx] += size[ry];
        components--;
        return true;
    }

    boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    int componentCount() {
        return components;
    }
}

// Kruskal's MST sketch: sort edges by weight, then union(u, v) each edge
// only if union() returns true (i.e., it does not close a cycle).

Pitfalls

• Forgetting path compression or union by rank/size: either one alone is fine (O(log n)), but skipping both degrades to O(n) per find on an adversarial union order (e.g., always union(i, i+1) in increasing order builds a straight chain).
• Comparing indices instead of roots: a common bug is checking x == y or parent[x] == parent[y] instead of find(x) == find(y) — two elements can be in the same set with different immediate parents.
• Stale size/rank after swapping roots: if you swap rx/ry to enforce "attach smaller under larger" but forget to also swap which size you update, you corrupt future union-by-size decisions and can reintroduce chains.
• Off-by-one on component counting: only decrement the component counter when union actually merges two distinct sets, not on every call.
• DSU has no built-in "split" or "remove": if the problem needs to undo a union or delete an edge, plain DSU cannot do it efficiently; that needs a different structure (e.g., a link-cut tree, or DSU-with-rollback for offline divide-and-conquer over time).
• Not resetting rank/size correctly when reusing a DSU instance across test cases — leftover state silently produces wrong connectivity answers.

When to use / when NOT — trade-offs vs. DFS-based connectivity

Use Union-Find when the workload is "many unions, many connectivity queries, edges only ever added, no path needed" — Kruskal's MST, "redundant connection," incremental network connectivity, offline grid flood-fill counted via merges. Prefer DFS/BFS when you need the shortest/actual path, need to handle edge removal, or only need connectivity computed once on a fixed, complete graph (a single O(V+E) pass is simpler to write and reason about than standing up a DSU for a one-shot query).

Takeaways

• DSU stores a forest of parent pointers, not an adjacency list; find walks to the root, union relinks roots.
• Union by rank/size bounds height at O(log n); adding path compression drops amortized cost to O(α(n)), effectively constant.
• union returning "already connected" is exactly a cycle-detection signal — that is the mechanism behind Kruskal's MST.
• DSU trades away path reconstruction and deletion support for near-O(1) incremental connectivity — reach for DFS/BFS when you need paths, distances, or edge removal.

Recall question

You are given m union operations to process on n elements, and only union by size is applied (no path compression). What is the tight worst-case bound on the height of any resulting tree, and why does always attaching the smaller-sized tree under the larger one's root guarantee that bound?

Authored for this guide; concepts and amortized-complexity analysis follow the standard treatment in Cormen/Leiserson/Rivest/Stein (CLRS), "Introduction to Algorithms," ch. 21 (Data Structures for Disjoint Sets), and Tarjan's original inverse-Ackermann analysis of union-find.