DSU Variants

Extensions of DSU that carry extra information or support extra operations.

Rollback DSU

Undo the last union. Required for offline dynamic connectivity.

struct RollbackDSU {
    vector<int> par, sz;
    vector<pair<int,int>> hist;                 // (merged root, its new parent)
    int comps;
 
    RollbackDSU(int n) : par(n), sz(n, 1), comps(n) { iota(par.begin(), par.end(), 0); }
 
    int find(int v) { while (par[v] != v) v = par[v]; return v; }   // NO path compression
 
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) { hist.push_back({-1, -1}); return false; }
        if (sz[a] < sz[b]) swap(a, b);
        hist.push_back({b, a});
        par[b] = a; sz[a] += sz[b]; comps--;
        return true;
    }
    void rollback() {
        auto [b, a] = hist.back(); hist.pop_back();
        if (b == -1) return;
        par[b] = b; sz[a] -= sz[b]; comps++;
    }
};

Path compression must go, because it makes arbitrarily many pointer changes per find and cannot be undone in $O (1)$ . Union by size alone still guarantees $O (lo g n)$ depth.

Weighted / parity DSU

Store each node’s value relative to its parent. Path compression accumulates the relative values.

struct ParityDSU {
    vector<int> par, rel, sz;                  // rel[v] = parity relative to par[v]
 
    pair<int,int> find(int v) {                // returns {root, parity relative to root}
        if (par[v] == v) return {v, 0};
        auto [r, p] = find(par[v]);
        par[v] = r; rel[v] ^= p;
        return {r, rel[v]};
    }
    // add the constraint "a and b differ by d"
    bool unite(int a, int b, int d) {
        auto [ra, pa] = find(a);
        auto [rb, pb] = find(b);
        if (ra == rb) return (pa ^ pb) == d;    // consistent?
        if (sz[ra] < sz[rb]) { swap(ra, rb); swap(pa, pb); }
        par[rb] = ra; rel[rb] = pa ^ pb ^ d; sz[ra] += sz[rb];
        return true;
    }
};

Uses:

Bipartiteness under edge insertion — an edge with $d = 1$ inside a component whose endpoints already have equal parity closes an odd cycle.
Constraints $a_{i} - a_{j} = c$ over a group — replace XOR with addition (be careful with the sign on path compression).
“Enemy of my enemy” relationship problems.
Modular constraints $a_{i} - a_{j} \equiv c (mod m)$ .

Persistent DSU

Keep every historical version. Built on a persistent array (a persistent segment tree over the par array), giving $O (lo g^{2} n)$ per operation with union by size and no path compression.

Used for “what were the components after the first $k$ edges?” queries, and inside some parallel-binary-search solutions. In practice, offline processing is nearly always simpler and faster.

DSU with distances to the root

Store dist[v] = number of edges to the parent; path compression sums them. Answers “how far is $v$ from its representative” — used in problems about merging chains, or the classic “cows in a stack” problem.

Small-to-large with sets

Not strictly DSU, but the same spirit: keep a set per component and merge the smaller into the larger.

if (s[a].size() < s[b].size()) swap(s[a], s[b]);
for (int x : s[b]) s[a].insert(x);
s[b].clear();

Each element moves $O (lo g n)$ times, so the total is $O (n lo g^{2} n)$ . Lets a component carry arbitrary aggregate information (distinct values, a heap, an ordered set) at the cost of a log factor. See DSU on Tree.

Comparison

Variant	Path compression	Extra info	Cost
Standard	yes	size	$O (α)$
Rollback	no	size	$O (lo g n)$
Parity / weighted	yes	relative value	$O (α)$
Persistent	no	versions	$O (lo g^{2} n)$
Small-to-large sets	—	arbitrary aggregate	$O (lo g^{2} n)$

See also: DSU · Dynamic Connectivity · Persistent Structures

whoashish's cp notes

Directory