Connectivity Problems

Connectivity problems: questions such as “Are nodes u and v in the same connected component?” or “How many connected components are there?” [Union-Find](/blog/algorithms/union-find/union-find-basics) (disjoint set union) supports union and find in nearly O(1) amortized and is the standard tool.

Operations

Find(x): Return the representative (root) of the component containing x. Use path compression: during find, attach nodes along the path to the root.
Union(x, y): Merge the components containing x and y. Use union by rank (or size): attach the smaller tree under the larger tree’s root.

With both heuristics, amortized time per operation is O(α(n)), effectively constant.

Template

Java
class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[py] < rank[px]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
    }
}

Number of Components

Start with n components (each node is its own). For each edge (u, v), call union(u, v). The number of components is the number of nodes x such that find(x) == x (or parent[x] == x before path compression).

Summary

Union-Find answers connectivity and component count after a series of unions. Use path compression and union by rank for near-constant time. Apply it to graphs, grids (cells as nodes, adjacent cells unioned), and “merge” operations over sets.