Union-Find

Groups as trees, trees in an array

The core idea is charmingly simple. Every group elects one member as its representative. That representative is the group's ID. Two items belong to the same group exactly when they have the same representative. All Union-Find machinery exists to answer who is your representative fast.

The implementation is a single int array called parent, where parent[i] holds the item that i points toward. Each group forms a little tree: items point up through parents until reaching the root, the one item that is its own parent (parent[root] == root) and that root is the representative. Initially every item is its own root, meaning n groups of one: parent[i] = i for all i.

Note what these trees are not: they are not the binary trees from earlier lessons, they have no ordering, and their shape carries no meaning. The only thing that matters is which root you reach by climbing.

class UnionFind {
    int[] parent;

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

Find, with path compression

Find(x) climbs the tree: follow parent[x], then that item's parent, until reaching an item that is its own parent. The root. The cost is the length of the climb, and left alone, unions can build tall skinny trees where climbs cost O(n).

Enter path compression, the first great optimization, one line of code: as find climbs to the root, it rewrites every item on the path to point directly at the root. The recursive version reads almost like the definition, if x is not a root, set parent[x] to the result of finding x's root, then return it. The first query along a long chain pays full price; every later query on those items is a single hop. The trees flatten themselves through ordinary use, like a shortcut path worn across a lawn.

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

Union: merge two groups

Union(a, b) merges the groups containing a and b. Find both roots; if they are already equal, the items share a group and nothing changes. Otherwise point one root's parent at the other, one assignment, and the two trees become one, with every member of both groups now climbing to a single representative.

Having union return whether a merge actually happened is a handy convention: a false return means a and b were already connected, which is exactly how you detect a cycle when processing a graph's edges. An edge whose endpoints are already connected would close a loop.

The second optimization, union by rank (or by size), chooses which root becomes the child: always hang the shorter tree under the taller one, so trees stay shallow. Combined with path compression, each operation costs amortized near-O(1). The true bound is the inverse Ackermann function, a value that never exceeds about 5 for any input that fits in the universe. For interviews, path compression alone is usually fast enough and keeps the code short.

boolean union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA == rootB) return false;
    parent[rootA] = rootB;
    return true;
}

The classic use case: connected components

A connected component is a cluster of nodes all reachable from one another. An island of the graph. Union-Find counts them without any traversal: start with n components, call union on each edge, and subtract one from the count every time union actually merges. After all edges, the counter holds the number of components; asking whether two specific nodes are connected is just find(a) == find(b).

You could do this with DFS, so when does Union-Find win? When connectivity is dynamic or interleaved. If edges arrive over time (accounts merging, computers cabling together, cells turning to land) a DFS answer goes stale after every new edge, while Union-Find absorbs each edge in near-constant time and stays current. It is also the engine inside Kruskal's minimum spanning tree algorithm and the standard tool for redundant connection and accounts merge problems. Its signature phrases: groups, merging, connected, and same set.

With Union-Find you now hold the full toolkit for connectivity. Trees for hierarchy, BFS and DFS for exploration, and DSU for dynamic grouping. The natural next step is layering algorithms on top: topological sort, shortest paths, and the classic graph patterns that interviews draw from again and again.

int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    int components = n;
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            components--;
        }
    }
    return components;
}

Frequently asked