Disjoint Set Union (Union-Find): Union by Rank + Path Compression & O(α(N)) Proof Intuition

Tree Height Invariants & The Inverse Ackermann Bound

A Disjoint Set Union (DSU) forest represents each set as a rooted tree where every node $x$ stores a parent pointer $\text{parent}[x]$, and the root $r$ of a set satisfies $\text{parent}[r] = r$ (or $\text{parent}[r] < 0$ in the negative-size encoding).

Why $\alpha(N)$ Arises: Rank Buckets & Ackermann Tower Collapse

Why isn't the amortized cost $O(1)$ or $O(\log^* N)$? Consider what happens when find(x) traverses a path $x = v_0 \to v_1 \to \dots \to r$. Path compression rewires $v_0, v_1, \dots$ to point directly to the root $r$. Notice that along any upward path, node ranks strictly increase: $\text{rank}(v_0) < \text{rank}(v_1) < \dots < \text{rank}(r)$.

Every time find traverses an edge $(u, p)$ that is not the last edge into the root, $\text{rank}(\text{parent}[u])$ strictly increases to $\text{rank}(r)$. Using a potential function grouped by levels of the Ackermann hierarchy $A_k(j)$ (where $A_0(j) = j+1$, $A_1(j) = 2j+1$, $A_2(j) = 2^{j+1}$, $A_3(j) = \text{tower of } 2\text{s}$), charging a traversal step to the level $k$ where $\text{rank}(\text{parent}[u]) \ge A_k(\text{rank}(u))$ proves that each node can pay for at most $O(\alpha(N))$ non-terminal pointer hops across its entire lifetime!

Complexity Matrix

Production Implementation: Single-Array Signed DSU with Path Compression

#include <vector>
#include <utility>

class DisjointSetUnion {
public:
    explicit DisjointSetUnion(int n) : parentOrNegSize(n, -1), numComponents(n) {}

    int find(int x) noexcept {
        int root = x;
        while (parentOrNegSize[root] >= 0) {
            root = parentOrNegSize[root];
        }
        while (x != root) {
            int next = parentOrNegSize[x];
            parentOrNegSize[x] = root;
            x = next;
        }
        return root;
    }

    bool unite(int a, int b) noexcept {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        // Remember: more negative means LARGER component size!
        if (parentOrNegSize[a] > parentOrNegSize[b]) {
            std::swap(a, b);
        }
        parentOrNegSize[a] += parentOrNegSize[b];
        parentOrNegSize[b] = a;
        --numComponents;
        return true;
    }

    bool connected(int a, int b) noexcept { return find(a) == find(b); }
    int componentSize(int x) noexcept { return -parentOrNegSize[find(x)]; }
    int components() const noexcept { return numComponents; }

private:
    std::vector<int> parentOrNegSize;
    int numComponents;
};