iv. Disjoint Set Union

Union-find maintains a partition under “merge two sets” and “which set is $x$ in”. With union by size and path compression, each operation is $O (α (n))$ amortized, which is optimal for pointer machines (Tarjan). Variants carry relative values, support undo, or keep history.

Standard

struct DSU {
    vector<int> p;                                    // p[x] < 0: root with size -p[x]
    DSU(int n) : p(n, -1) {}
    int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (p[a] > p[b]) swap(a, b);
        p[a] += p[b]; p[b] = a;
        return true;
    }
    int size(int x) { return -p[find(x)]; }
};

Union by size alone gives $O (lo g n)$ depth. Path compression alone gives $O (lo g n)$ amortized. Together: $O (α (n))$ . For a path of $1 0^{6}$ unions, the recursive find can be deep before compression happens; use an iterative find if the stack is tight.

Proof: union by size alone bounds depth by $O (lo g n)$

unite always attaches the smaller-size root under the larger-size root, so every time a node’s depth increases by one (it moves to being a child of a new root during a union), the size of the tree it is now part of is at least double what its old tree’s size was — it was in the tree being attached (the smaller one, size $\leq s$ ) and the resulting tree has size $\geq 2 s$ . Since size is bounded by $n$ , a node’s depth can increase at most $lo g_{2} n$ times over the whole run, so every tree has depth $O (lo g n)$ and every find (even with no compression) costs $O (lo g n)$ . $■$

Proof (cited): path compression alone is $O (lo g n)$ amortized

Without union-by-size, a worst-case adversarial union order can build a tree of depth $Θ (n)$ before any compression happens (e.g. unite $1 \to 2 \to 3 \to \dots$ one at a time, always making the new element a child of the existing chain’s root — no rank information to prevent this). Path compression on a single find down a depth- $d$ chain is $O (d)$ to flatten but makes every subsequent find on those nodes $O (1)$ , and the standard amortized argument (charging the cost of each find against how much shallower it leaves the tree, formalised with a potential function over node depths) gives $O (lo g n)$ amortized per operation — a real but somewhat involved argument not reproduced in full here; the key fact worth remembering is that path compression alone, without union by size, is already enough to avoid the $O (n)$ worst case per operation.

Combined, union by size and path compression give the famous $Θ (α (n))$ amortized bound (Tarjan, 1975) — optimal for any pointer-based structure — via a weight-function argument assigning each node to one of $O (α (n))$ “levels” based on how fast an Ackermann-like function grows relative to subtree size; not reproduced here, since for any $n$ that fits in memory $α (n) \leq 4$ and the practical takeaway (“effectively constant”) is what matters.

Uses

Problem	How
connected components, offline	unite all edges
Kruskal	add an edge iff `unite` succeeds
cycle in an undirected graph	the first edge that fails to unite
connectivity with deletions, offline	reverse time
”paint $[l, r]$ but skip painted cells”, “next free slot”	DSU as a pointer to the next unpainted index: each cell is touched once
merging intervals, grid percolation	cells as elements, plus virtual nodes for borders
equivalence with contradictions	parity / weighted DSU
offline LCA	Tarjan’s algorithm (LCA)
Kruskal reconstruction tree	new node per union (KRT)
number of components	maintain a counter, decremented on every successful `unite`
component sizes	`size(find(v))`
image / grid connected components	an alternative to flood fill: unite every pair of adjacent same-colour cells

DSU on a grid: map $(r, c)$ to $r \cdot C + c$ and unite as usual; add one virtual node for “outside the grid” when the problem asks about connections to the border (common in percolation and island problems).

Next free slot:

// nxt[i] = smallest unused index >= i (n is a sentinel)
int get(int i) { return nxt[i] == i ? i : nxt[i] = get(nxt[i]); }
for (int i = get(l); i <= r; i = get(i + 1)) { paint(i); nxt[i] = i + 1; }

Weighted (potential) DSU

Store each node’s value relative to its parent and accumulate along compression. It handles constraints $x_{a} - x_{b} = d$ over any group (sums, XOR, modular arithmetic, even permutations composed).

struct WeightedDSU {                 // maintains pot[x] = value(x) - value(root)
    vector<int> p; vector<ll> pot;
    WeightedDSU(int n) : p(n, -1), pot(n, 0) {}
    int find(int x) {
        if (p[x] < 0) return x;
        int r = find(p[x]); pot[x] += pot[p[x]]; return p[x] = r;
    }
    // add constraint value(b) - value(a) = d; returns false on contradiction
    bool unite(int a, int b, ll d) {
        int ra = find(a), rb = find(b);
        d += pot[a] - pot[b];               // now value(rb) - value(ra) = d
        if (ra == rb) return d == 0;
        if (p[ra] > p[rb]) swap(ra, rb), d = -d;
        p[ra] += p[rb]; p[rb] = ra; pot[rb] = d;
        return true;
    }
    ll diff(int a, int b) { return pot[b] - pot[a]; }   // valid after find(a), find(b) in the same set
};

Proof: weighted DSU maintains pot[x] = value(x) - value(root) correctly

By induction on the sequence of operations. find(x) recurses to the root $r$ , and by the inductive hypothesis pot[p[x]] already equals $v a l u e (p [x]) - v a l u e (r)$ once p[x] has been fully compressed to point near $r$ ; adding it to the old pot[x]=value(x)-value(p[x]) gives $v a l u e (x) - v a l u e (r)$ exactly, which is then cached as the new pot[x] when x is repointed directly at $r$ — so compression never changes what pot[x] logically represents, only how many hops it takes to recompute it. In unite(a,b,d), after finding roots $r_{a}, r_{b}$ , d is adjusted by pot[a]-pot[b] to convert the constraint “value(b)-value(a)=d” into “value( $r_{b}$ )-value( $r_{a}$ ) = d” (substituting $v a l u e (a) = v a l u e (r_{a}) + p o t [a]$ and likewise for $b$ ); if $r_{a} = r_{b}$ this is a redundant constraint, correctly checked against the already-implied value ( $d = 0$ required for consistency); otherwise attaching $r_{a}$ under $r_{b}$ (or vice versa, negating $d$ ) with $p o t [r_{a}] = \pm d$ makes the new root relationship exactly $v a l u e (r_{a}) - v a l u e (r_{b}) = \mp d$ , consistent with the derived constraint. Since every pot value is always expressed relative to the current root and updated consistently on every compression and union, diff(a,b) = pot[b]-pot[a] after calling find on both equals $(v a l u e (b) - v a l u e (root)) - (v a l u e (a) - v a l u e (root)) = v a l u e (b) - v a l u e (a)$ . $■$

Parity DSU is the special case over $Z_{2}$ with XOR. Uses: online bipartiteness (an edge inside a component with equal parities closes an odd cycle), “friend/enemy” relations, checking systems $x_{i} - x_{j} = c$ , and food-chain style $Z_{3}$ relations.

Distance to the root is the same accumulation trick specialised to unweighted edges: store dist[v] = number of edges to the parent, and path compression sums it exactly as pot does above. Answers “how far is $v$ from its representative” — the classic “cows in a stack” problem, and merging chains in general.

Rollback DSU

For undo (offline dynamic connectivity, segment tree over time, divide and conquer): union by size, no path compression, and a history stack.

struct RollbackDSU {
    vector<int> p; vector<pair<int, int>> st;          // (child root, old parent size) or (-1, -1)
    RollbackDSU(int n) : p(n, -1) {}
    int find(int x) { while (p[x] >= 0) x = p[x]; return x; }
    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) { st.push_back({-1, -1}); return false; }
        if (p[a] > p[b]) swap(a, b);
        st.push_back({b, p[b]}); p[a] += p[b]; p[b] = a;
        return true;
    }
    void undo() {
        auto [b, sb] = st.back(); st.pop_back();
        if (b < 0) return;
        int a = p[b]; p[a] -= sb; p[b] = sb;
    }
    int snapshot() { return sz(st); }
    void rollback(int t) { while (sz(st) > t) undo(); }
};

Every find is $O (lo g n)$ . Recording a dummy entry for failed unions keeps “one undo per apply”, which the queue-undo trick requires (Offline Techniques). Parity and weights combine with rollback the same way.

Persistent DSU

Fat nodes or a persistent array (persistent segment tree over p) with union by size and no compression: $O (lo g^{2} n)$ per operation, every version queryable. Used for “what were the components after the first $k$ edges” queries, and inside some parallel-binary-search solutions. Offline alternatives (sorting queries by version, a version tree DFS with rollback) are usually simpler and faster in practice: build the tree of versions, DFS it applying each version’s union on entry and undoing on exit.

Small-to-large merging of sets

Give each component a set, map or vector and always move the smaller into the larger. Each element moves $O (lo g n)$ times, so the total is $O (n lo g n)$ moves ( $O (n lo g^{2} n)$ with set). This lets components carry anything: distinct colours, sorted positions, heaps.

Proof: small-to-large moves each element $O (lo g n)$ times

Every time an element is moved, it is moved as part of the smaller of the two merging sets, so the set it ends up in has size at least double the size of the set it was just moved out of (size $\geq 2 \times$ the smaller set’s size, by definition of “smaller”). An element starts in a set of size $\geq 1$ and the set containing it can have size at most $n$ , so it can be on the “moved” side at most $lo g_{2} n$ times before its component’s size would have to exceed $n$ . Summing over all $n$ elements gives $O (n lo g n)$ total moves; with a vector/array each move is $O (1)$ (append), giving $O (n lo g n)$ total, while a set move costs $O (lo g n)$ per element, giving $O (n lo g^{2} n)$ . $■$

What DSU can’t do

Split a set. Use reverse time, offline deletion, or link-cut trees.
Path information between two elements in the same set. Use a spanning forest + LCA, or a link-cut tree.
Directed reachability: that’s SCC territory.

whoashish's cp notes

Directory