Union-Find (Disjoint Set)

Data Structures O(α(n)) O(n)

Forest of sets: find walks to a root and flattens the path behind it, union hangs the lower-rank root under the higher one.

UnionsFind

1/37

makeSets(8): every element is its own root with rank 0.

InvariantEach element points towards its set's root; two elements are in one set exactly when they share that root.

currentcompareinsertremoverotate

union-find.c

int parent[N], rank_[N];
 
void makeSets(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank_[i] = 0;
    }
}
 
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   /* compress */
    return parent[x];
}
 
void unionSets(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;              /* same set */
    if (rank_[ra] < rank_[rb]) {
        parent[ra] = rb;
    } else if (rank_[ra] > rank_[rb]) {
        parent[rb] = ra;
    } else {
        parent[rb] = ra;
        rank_[ra]++;
    }
}

How Union-Find (Disjoint Set) works

Each set is a tree; the root is the set's representative. find(x) walks to the root, union links one root under the other. Path compression makes every visited node point straight at the root, flattening trees as a side effect of use.

Best case

Flattened trees — find is a single hop: effectively O(1).

Worst case

With union by rank + path compression: amortized O(α(n)) — inverse Ackermann, ≤ 4 in practice.

When to use it

Dynamic connectivity: Kruskal's MST, cycle detection, grouping equivalent items.