Union-find (disjoint set)

Track groups of items as they merge, and answer "are these two already in the same group?" in near constant time.

The idea

Every item starts as the root of its own one-item set. Find walks parent pointers up to the root, compressing the path on the way so future finds are faster. Union attaches the root of one set under the root of the other, choosing the shorter tree to attach so trees stay shallow.

Code

public class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x)
            parent[x] = Find(parent[x]); // path compression: point straight at the root
        return parent[x];
    }
    public void Union(int a, int b) {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return;
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra; // attach the shorter tree under the taller one
        if (rank[ra] == rank[rb]) rank[ra]++;
    }
}

Tips

• Path compression and union by rank each make the operations fast; together they give the near constant O(α(V)) amortised time.
• .NET has no built-in union-find. It is about 15 lines, as above.

In the .NET library

A common bug is compressing the path in Find but forgetting union by rank (or the reverse): either one alone is fast enough in practice, but without the other, a bad input order can still build a tall, slow tree.