Disjoint-set data structure

The Disjoint-set data structure, also known as a union-find or merge-find set, is a foundational abstract data structure that tracks a partition of a set into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, merge existing sets, and determine whether two elements reside in the same subset. Through the combined application of path compression and union by rank (or size), its amortized time complexity per operation is bounded by the inverse Ackermann function, rendering it effectively constant for all practical problem sizes.

class DisjointSet {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    int setCount;

public:
    explicit DisjointSet(int n) : setCount(n) {
        parent.resize(n);
        rank.assign(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
};

    int find(int i) {
        if (parent[i] == i)
            return i;
        // Path compression: point node directly to the root
        return parent[i] = find(parent[i]);
    }

    bool unionSets(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            setCount--;
            return true;
        }
        return false;
    }

void runTests() {
    DisjointSet ds(10);
    assert(ds.find(0) != ds.find(1));
    ds.unionSets(0, 1);
    assert(ds.find(0) == ds.find(1));
    ds.unionSets(1, 2);
    assert(ds.find(0) == ds.find(2));
    std::cout << "All tests passed successfully." << std::endl;
}

    int safeFind(int i) {
        if (i < 0 || i >= static_cast<int>(parent.size())) {
            throw std::out_of_range("Element index out of bounds");
        }
        return find(i);
    }

Mathematical Foundations & Amortized Complexity

The efficiency of the disjoint-set data structure relies on two heuristics applied to the underlying forest of trees: Union by Rank (or Size) and Path Compression. Let n be the number of elements and m be the total number of operations (Find and Union). Without optimizations, a tree can degenerate into a linear linked list, yielding worst-case time complexity of O(n) per operation. Union by rank keeps tree height bounded by O(log n). When combined with path compression during the Find operation—which alters pointers along the access path to point directly to the root—the worst-case time complexity per operation drops to the inverse Ackermann function, denoted as O(alpha(n)). Because alpha(n) <= 4 for any practical input size encountered in physical computing (since Ackermann's function grows at a hyper-exponential rate), the operations execute in amortized constant time, O(1).

Architectural Applications

Disjoint-set data structures are critical across systems and algorithms engineering. Prime use cases include Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph, dynamic connectivity queries in networks, image segmentation in computer vision, unification algorithms in type inference engines, and tracking connected components in grid-based simulations. In memory-constrained environments, array-backed disjoint-set structures eliminate pointer overhead, maximizing CPU cache locality.

Production Anti-Patterns & Failure Modes

Common pitfalls in production implementations include omitting path compression (leading to degraded O(log n) or O(n) performance under heavy workloads), failing to update rank or size correctly during union operations (which ruins tree balancing guarantees), and mutating data structures across threads without proper synchronization primitives. In high-concurrency environments, fine-grained locking or lock-free transactional memory models must be employed to prevent race conditions during path compression pointer updates.