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.

Working Principle

Union-Find (Disjoint Set Union, DSU) maintains a partition of elements into disjoint groups and supports two operations: find(x) — which group is \(x\) in? (represented by a canonical "representative" element) — and union(x, y) — merge \(x\)'s and \(y\)'s groups. The naive implementation represents each group as a tree (via parent pointers), with find walking up to the root and union attaching one root under the other.

Two Optimizations That Change Everything

Union by rank (or size): when merging two groups, always attach the shorter (or smaller) tree under the taller (or larger) tree's root, never the reverse. This alone bounds tree height at \(O(\log n)\), since a tree can only grow taller by merging with an equally tall tree, at most \(\log n\) times.

Path compression: every time find(x) walks up to the root, re-point every node visited along the way directly to that root. Future find calls on any of those nodes become instant. This is a self-optimizing data structure — it gets flatter, and faster, the more it's used.

flowchart LR
    subgraph Before["Before find(D)"]
        A1["A (root)"] --- B1["B"] --- C1["C"] --- D1["D"]
    end
    subgraph After["After find(D): path compressed"]
        A2["A (root)"] --- B2["B"]
        A2 --- C2["C"]
        A2 --- D2["D"]
    end
            

The Inverse Ackermann Bound

The Ackermann function \(A(m,n)\) grows faster than any primitive recursive function — faster than exponentials, faster than towers of exponentials. Its inverse, \(\alpha(n)\), therefore grows unimaginably slowly: \(\alpha(n) \leq 4\) for every \(n\) up to more digits than there are atoms in the observable universe. In every practical sense, \(O(\alpha(n))\) is "constant time" — but it is a genuinely different (and strictly larger) complexity class than true \(O(1)\), which is exactly why the distinction earned its own theorem rather than being waved away.

$$\text{Time (m operations, n elements): } O(m \cdot \alpha(n)) \qquad \text{Space: } O(n)$$

Implementation

class UnionFind:
    def __init__(self, elements):
        self.parent = {e: e for e in elements}
        self.rank = {e: 0 for e in elements}
        self.count = len(elements)   # number of distinct groups remaining

    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              # already in the same group
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx           # union by rank
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

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

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}

#include <vector>
#include <numeric>
using namespace std;

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) {
        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;              // already connected
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;                         // union by rank
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

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: 0-1-2-3 merged transitively
    return 0;
}

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

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

    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;               // already connected
        if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
        parent[ry] = rx;                           // union by rank
        if (rank[rx] == rank[ry]) rank[rx]++;
        count--;
        return true;
    }

    boolean connected(int x, int y) { return find(x) == find(y); }

    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}
    }
}

Real-World Applications

Exercises

1. Implement Union-Find with path compression but without union by rank (always attach the second tree under the first), and construct a sequence of unions that produces a long chain — measure how much slower find becomes.
2. Explain why count (the number of remaining groups) can be maintained in \(O(1)\) extra work per successful union call, and why it's useful for efficiently answering "are all elements now in one group?"
3. Trace through the percolation case study: build a small 3×3 grid, "open" cells one at a time in some order, and determine after each step whether the top row is connected to the bottom row.
4. Challenge: Implement union by size instead of union by rank (track subtree size, attach the smaller tree under the larger) and prove it gives the same \(O(\log n)\) height bound as union by rank, even though it tracks a different quantity.

Limitations