Union-Find (Disjoint Set Union)

A Bit of History

The Union-Find data structure was introduced by Bernard Galler and Michael Fischer in a short 1964 paper on compiler design, motivated by tracking equivalence classes of program variables. Over the following decade, researchers including M. D. McIlroy, Robert Morris, and independently J. D. Tritter contributed the "union by rank/size" and "path compression" optimizations you'll use here. But the full story of why those optimizations are so effective wasn't nailed down until 1975, when Robert Tarjan (already a familiar name from Parts 6 and 8) proved that a sequence of \(m\) operations on \(n\) elements takes \(O(m \, \alpha(n))\) time, where \(\alpha\) is the inverse Ackermann function — a function that grows so slowly that \(\alpha(n) \leq 4\) for any \(n\) you could ever physically enumerate, even though it is not, strictly speaking, a constant.

The Forest Model

Union–Find stores a partition: every element belongs to exactly one set, sets never overlap, and together they contain every element. Each set is represented as a rooted tree. The root is the set's representative and satisfies parent[root] == root.

Working Principle

The forest representation needs only one parent entry per element. A root points to itself; every other node points one step closer to its root. The fundamental equivalence is:

$$x \text{ and } y \text{ are connected} \iff \operatorname{find}(x)=\operatorname{find}(y).$$

Calling union(x,y) first replaces both arguments by their roots. If the roots are equal, the operation changes nothing and returns false. Otherwise it links the two trees, updates root-only metadata such as size, decrements the number of sets, and returns true.

Two Optimizations That Change Everything

1. Union by size or rank

When two roots differ, attach the root of the smaller tree below the root of the larger tree. A node's depth can increase only when its entire set joins a set at least as large, so the size of its containing set at least doubles. That can happen at most $\lfloor\log_2 n\rfloor$ times.

Rank is an alternative upper-bound heuristic for height. When two unequal ranks merge, the larger rank stays unchanged; when equal ranks merge, the winning root's rank increases by one. After path compression, rank is no longer the tree's exact current height—and it does not need to be.

2. Path compression

A find(x) first reaches the root, then redirects every parent pointer on that search path straight to the root. The partition does not change; only its internal representation becomes flatter.

The deliberately tall chain below isolates compression's effect. Union by size would already make such a five-node chain difficult to create through normal unions.

The Inverse Ackermann Bound

The Ackermann function grows extraordinarily quickly; its inverse $\alpha(n)$ grows extraordinarily slowly. For every input size that can arise in physical computation, $α(n)$ is a tiny single-digit value. That makes Union–Find effectively constant-time in practice, but the mathematical bound is still not literal $O(1)$.

For $n$ elements and a sequence of $m$ operations using both optimizations:

$$\text{Total time: } O((n+m)\alpha(n)) \qquad \text{Space: } O(n)$$

Implementation

The listings use union by size. Only roots have meaningful size values; always call find before reading or updating that metadata.

class UnionFind:
    def __init__(self, elements):
        items = list(dict.fromkeys(elements))  # stable deduplication
        self.parent = {e: e for e in items}
        self.size = {e: 1 for e in items}
        self.count = len(items)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

    def component_size(self, x):
        return self.size[self.find(x)]

uf = UnionFind(["A", "B", "C", "D", "E"])
uf.union("A", "B")
uf.union("C", "D")
print(uf.connected("A", "B"))   # True
print(uf.connected("A", "C"))   # False
uf.union("B", "C")
print(uf.connected("A", "D"))   # True (A-B-C-D all merged transitively)
print(uf.count)                 # 2 groups remain: {A,B,C,D} and {E}
print(uf.component_size("D")) # 4

#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>
#include <numeric>
using namespace std;

class UnionFind {
    vector<int> parent, size_;
    int count_;
public:
    UnionFind(int n) : parent(n < 0 ? 0 : n), size_(n < 0 ? 0 : n, 1), count_(n) {
        if (n < 0) throw invalid_argument("n must be non-negative");
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

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

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size_[rx] < size_[ry]) swap(rx, ry);
        parent[ry] = rx;
        size_[rx] += size_[ry];
        --count_;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int componentSize(int x) { return size_[find(x)]; }
    int count() const { return count_; }
};

int main() {
    UnionFind uf(5);   // elements 0..4
    uf.unite(0, 1);
    uf.unite(2, 3);
    uf.unite(1, 2);
    bool result = uf.connected(0, 3);  // true
    int size = uf.componentSize(3);    // 4
    cout << boolalpha << result << " size=" << size
         << " components=" << uf.count() << '\n';
    return 0;
}

class UnionFind {
    int[] parent, size;
    int count;

    UnionFind(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        parent = new int[n];
        size = new int[n];
        count = 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]);  // path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (size[rx] < size[ry]) { int t = rx; rx = ry; ry = t; }
        parent[ry] = rx;
        size[rx] += size[ry];
        count--;
        return true;
    }

    boolean connected(int x, int y) { return find(x) == find(y); }
    int componentSize(int x) { return size[find(x)]; }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(1, 2);
        System.out.println(uf.connected(0, 3));  // true
        System.out.println(uf.count);             // 2 groups: {0,1,2,3} and {4}
        System.out.println(uf.componentSize(3));  // 4
    }
}

Real-World Applications

The Monotone Sweet Spot

DSU is ideal when relationships are added and never removed. If edges arrive as a stream, every successful union monotonically coarsens the partition. It answers connectivity, component count, and root-level aggregates without searching the full component on each query.

Variants & Limitations

Standard path-compressed DSU cannot split a component efficiently because its forest remembers the partition, not the history of original edges. Rollback DSU is the important exception to “no undo”: attach by size, record each changed field on a stack, and restore a previous snapshot. Avoid ordinary path compression because one find could rewrite many unlogged pointers.

Pitfalls & Debugging

Exercises