Disjoint Sets

A disjoint-set union structure maintains a partition of elements into non-overlapping sets.

• makeSet(x) creates a singleton.
• find(x) returns a representative of x's set.
• union(a, b) merges two sets when distinct.

Forest representation

Each element points to a parent; a root represents its set. Two complementary optimizations make operations extremely efficient:

• union by rank or size attaches the smaller/shallow tree below the other;
• path compression redirects visited nodes toward the root during find.

final class DisjointSet {
    private final int[] parent;
    private final int[] size;

    DisjointSet(int n) {
        if (n < 0) throw new IllegalArgumentException("negative size");
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

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

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

Across a sequence of operations, the amortized time is O(α(n)), where the inverse Ackermann function grows so slowly that it is tiny for practical input sizes. This is not literally constant in the mathematical sense.

Applications

Use disjoint sets for incremental undirected connectivity, Kruskal's minimum spanning-tree algorithm, and grouping equivalence classes. They do not directly support edge deletion or path reconstruction.