8 / 8 Union-Find (Disjoint Set Union)

Rollback Refuses Compression

Offline dynamic connectivity builds a segment tree over time, applies edges when a DFS enters a node and undoes them when it leaves. The DSU it uses looks like this:

int find_set(int v) {
    return (v == p[v]) ? v : find_set(p[v]);   // no compression
}

bool unite(int v, int u) {
    v = find_set(v); u = find_set(u);
    if (v == u) return false;
    comps--;
    if (rnk[v] > rnk[u]) swap(v, u);
    op.push(dsu_save(v, rnk[v], u, rnk[u]));   // record for rollback
    p[v] = u;
    if (rnk[u] == rnk[v]) rnk[u]++;
    return true;
}

Path compression is deliberately absent. Why?

A

The segment tree already bounds each edge to O(log n) nodes, so the total number of find_set calls is small enough that compression would not pay for itself.

B

The near-constant bound that compression buys is amortized, and rollback destroys amortization: a caller can undo a costly flatten right after paying for it and repeat. Union by rank alone gives a true O(log n) worst case per find, which survives being undone.

C

Compression overwrites the old parent links, so the information needed to restore the previous state is gone.

D

After a rollback a compressed parent pointer would point into a component that no longer exists, so find_set would return a wrong root.