Disjoint Set Union

DSU (union-find) maintains a partition of $n$ elements under two operations: find(v) — which set is $v$ in — and unite(a,b) — merge two sets. With both optimisations, effectively $O(\alpha (n))$ per operation, where $\alpha$ is the inverse Ackermann function and $\alpha (n)<5$ for any $n$ you will ever see.

Implementation

struct DSU {
    vector<int> par, sz;
    int comps;
 
    DSU(int n) : par(n), sz(n, 1), comps(n) { iota(par.begin(), par.end(), 0); }
 
    int find(int v) { return par[v] == v ? v : par[v] = find(par[v]); }   // path compression
 
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);                                   // union by size
        par[b] = a;
        sz[a] += sz[b];
        comps--;
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
    int size(int v) { return sz[find(v)]; }
};

unite returning false when the elements were already together is what makes Kruskal a five-line loop.

The two optimisations

Optimisation	Alone	Together
Neither	$O(n)$ per op
Union by size/rank only	$O(\log n)$
Path compression only	$O(\log n)$ amortized
Both		$O(\alpha (n))$ amortized

Union by size keeps the tree shallow; path compression flattens it on the way back up. Tarjan proved the combined bound is $\Theta (\alpha (n))$ amortized, and that this is optimal for any pointer-based structure.

Path compression breaks rollback

If you need to undo unions (for offline dynamic connectivity), you must drop path compression and use union by size only — find becomes $O(\log n)$, which is the price of undo. See DSU Variants.

What DSU is for

Problem	How
Connected components	unite every edge
Kruskal MST	add an edge iff unite succeeds
Cycle detection (undirected)	an edge whose endpoints are already united closes a cycle
Number of components	maintain a counter
Component sizes	sz[find(v)]
Offline LCA	union subtrees as the DFS finishes them
Percolation / grid merging	treat cells as elements
”Merge intervals” / “next free slot”	see below
Equations $a_i=a_j$ with contradictions	unite, then check
Image connected components	flood fill alternative

The “next free slot” trick

A remarkably useful idiom: use DSU as a pointer to the next unused position.

// par[i] = the smallest free index >= i
int nextFree(int i) { return par[i] == i ? i : par[i] = nextFree(par[i]); }
void occupy(int i) { par[i] = i + 1; }        // point past this slot

This solves “assign each request the earliest available slot” in near-linear time, and turns “paint the range $[l,r]$, but only cells not yet painted” into an amortized $O(n\alpha )$ sweep — each cell is painted once and then skipped forever.

// paint [l, r] with colour c, skipping already-painted cells
for (int i = nextFree(l); i <= r; i = nextFree(i + 1)) {
    colour[i] = c;
    occupy(i);
}

DSU on a grid

Map $(r,c)$ to $r\cdot C+c$. Add a virtual node for “outside the grid” when the problem asks about connections to the border — a common trick in percolation and island problems.

What DSU cannot do

• Split a set (there is no separate operation). If you need deletions, process the queries in reverse, or use offline dynamic connectivity.
• Answer queries about paths between elements — that needs link-cut trees.
• Handle directed reachability — see SCC.

See also: DSU Variants · Dynamic Connectivity · Kruskal