Core Data Structures

Disjoint Sets (Union-Find)

A union-find (disjoint-set) structure tracks a partition of elements into disjoint groups, supporting union (merge two groups) and find (which group is this element in) in almost-constant amortized time — with two small optimizations doing all the work.

Backed by a simple array: each element points to a parent; a root (self-parent) identifies its group
find(x) walks parent pointers to the root; union(x, y) links one root under the other
Union by rank/size: always attach the smaller tree under the bigger one, keeping trees shallow
Path compression: during find, point every visited node directly at the root, flattening future lookups
Both optimizations together give O(α(n)) amortized per operation, where α is the inverse Ackermann function — practically a constant ≤ 4 for any n that fits in the universe
The classic application is Kruskal's minimum spanning tree algorithm (Minimum Spanning Trees) and cycle detection in undirected graphs

Union-find with path compression and union by rank

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // each element starts as its own root
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;                              // already same set
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }  // ra has >= rank
        parent[rb] = ra;                                   // attach smaller under bigger
        if (rank[ra] == rank[rb]) rank[ra]++;
    }
}

Path compression alone, without union by rank, already gives an amortized O(log n) bound; union by rank alone gives the same. Combined, the two produce the famously tiny O(α(n)) bound — the inverse Ackermann function grows so slowly that it never exceeds 4 for any input size that could physically exist, so union-find operations are, in every practical sense, constant time.

Effect of the two optimizations
Optimizations applied	Amortized cost per operation
Neither	O(n) worst case — a degenerate chain
Union by rank/size only	O(log n)
Path compression only	O(log n) amortized
Both	O(α(n)) — effectively O(1)