Union-Find (Disjoint Sets)

Union-Find (Disjoint Sets)

Union-Find, also called a disjoint set union (DSU), keeps track of elements split into non-overlapping groups, and answers one question very fast: "are these two elements in the same group?" It supports two operations:

• union(a, b): merge the groups containing a and b.
• find(a): return a representative (the "root") of a's group. Two elements are in the same group exactly when their roots are equal.

It's the natural tool whenever connections arrive over time and you need connectivity questions answered along the way: networks being wired up, accounts being linked by shared emails, edges added to a graph while you watch for the first one that forms a cycle.

The idea: a forest of parent pointers

Each group is a tree, and every element points to a parent. The root points to itself and names the group. find follows parent pointers up to the root, and union makes one root point to the other.

parent: [0, 0, 1, 3, 3]        group {0,1,2}: 2 → 1 → 0 (root 0)
                               group {3,4}:   4 → 3      (root 3)
union(2, 4): root(2)=0, root(4)=3 → set parent[3] = 0 → all five are one group

Done naively, the trees can become long chains, and find degrades to O(n). Two small optimizations fix that.

The two optimizations

Path compression (in find): after finding the root, make every node on the path point directly to it. The next find on any of them takes one step.

Union by rank or size (in union): attach the smaller or shallower tree under the larger one, never the other way round, so trees stay flat.

With both, a sequence of m operations on n elements takes O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that α(n) ≤ 4 for any input that fits in the universe, so in practice each operation is effectively constant time.

class UnionFind {
    private final int[] parent, size;
    private int groups;

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

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];          // walk to the root
        while (parent[x] != root) {                                 // path compression (iterative:
            int next = parent[x]; parent[x] = root; x = next;       //  no stack overflow on long chains)
        }
        return root;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                                 // already connected
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }   // union by size: small under large
        parent[rb] = ra;
        size[ra] += size[rb];
        groups--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
    int groups()                    { return groups; }
    int sizeOf(int x)               { return size[find(x)]; }
}

Returning false from union when the two are already connected is a small design choice that makes cycle detection a one-liner.

Problems it solves directly

Number of connected components: start with n groups, and union each edge. What's left is the answer.

int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] e : edges) uf.union(e[0], e[1]);
    return uf.groups();
}

Redundant Connection: in a graph that was a tree plus one extra edge, find that edge. The first edge whose endpoints are already connected closes a cycle:

int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);        // nodes are 1..n
    for (int[] e : edges) if (!uf.union(e[0], e[1])) return e;
    return new int[0];
}

Graph Valid Tree: a graph on n nodes is a tree if it has exactly n − 1 edges and no union ever fails (no cycles). Those two facts together imply it's connected.

Kruskal's minimum spanning tree: sort edges by weight, and add each one whose endpoints are in different groups. Union-Find is what makes each "would this create a cycle?" check cheap.

Accounts Merge: each account is a list of emails, and accounts that share any email belong to the same person. Union all emails within an account, then group emails by root:

List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> id = new HashMap<>();           // email → index
    Map<String, String> owner = new HashMap<>();          // email → name
    for (List<String> acc : accounts)
        for (int i = 1; i < acc.size(); i++) {
            id.putIfAbsent(acc.get(i), id.size());
            owner.put(acc.get(i), acc.get(0));
        }

    UnionFind uf = new UnionFind(id.size());
    for (List<String> acc : accounts)
        for (int i = 2; i < acc.size(); i++) uf.union(id.get(acc.get(1)), id.get(acc.get(i)));

    Map<Integer, TreeSet<String>> byRoot = new HashMap<>();
    id.forEach((email, idx) -> byRoot.computeIfAbsent(uf.find(idx), r -> new TreeSet<>()).add(email));

    List<List<String>> result = new ArrayList<>();
    for (TreeSet<String> emails : byRoot.values()) {
        List<String> merged = new ArrayList<>();
        merged.add(owner.get(emails.first()));
        merged.addAll(emails);                            // TreeSet → sorted, as the problem requires
        result.add(merged);
    }
    return result;
}

Mapping arbitrary keys (strings, coordinates) to integer indexes first lets you reuse the array-based implementation.

Grids: number each cell as row * cols + col and union neighbouring land cells. "Number of Islands II", where land is added one cell at a time with the count needed after each addition, is where Union-Find beats re-running DFS every time.

Union-Find vs DFS/BFS

Follow-up questions this topic invites — and their answers

Q: What do path compression and union by rank each contribute? A: Union by rank or size keeps trees shallow (height O(log n)), so find is O(log n) even without compression. Path compression flattens paths as they're used. Together they give O(α(n)) amortized per operation. Either alone is already a big improvement over the naive version.

Q: Can Union-Find support removing an edge or splitting a set? A: Not efficiently. It only merges. For deletions, you process queries offline in reverse (turning deletions into additions), or use more complex dynamic-connectivity structures.

Q: Why is iterative find sometimes preferred over recursive? A: Before compression kicks in, a path can be long. Recursion depth equal to that path length can overflow the stack on large inputs. The two-pass iterative version (find the root, then repoint every node on the path) has no depth limit.

Q: How do you detect a cycle in an undirected graph with Union-Find? A: Process edges one by one. If an edge's two endpoints already have the same root, adding it closes a cycle. For directed graphs this doesn't work; use DFS with recursion-state colouring or Kahn's algorithm instead.

Q: How would you track the size of the largest group as unions happen? A: Keep a size array for roots (as above), update it on every union, and maintain a running maximum. Each union is O(α(n)), and the maximum is O(1) to read.