Rollback Union-Find and Offline Dynamic Connectivity

Path compression is irreversible. A find that rewrites a parent link destroys the information needed to put it back, and there is no compact way to record the rewrite because the same slot may be rewritten repeatedly within one traversal. A disjoint-set structure that must undo unions therefore gives up compression entirely and pays for it with a height bound instead: union by size or rank without compression, plus a log of the few writes each union performs.

The resulting structure is not a curiosity. It is the engine behind offline dynamic connectivity, where a graph’s edges arrive and depart and the question is whether two vertices are connected at each point in time. Fully dynamic connectivity — insertions and deletions interleaved with queries, answered online — does have polylogarithmic algorithms, but they maintain a spanning forest with Euler-tour trees and are substantially heavier than anything in this cluster. When every query is known in advance, the offline problem reduces to a sequence of reversible merges over an interval decomposition, and that reduction is both simpler and faster than the online algorithms.

What a union actually writes

In a parent array with union by size, one union touches exactly two slots: the surviving root’s size, and the absorbed root’s parent pointer. Recording those two writes and their previous values is enough to restore the structure exactly.

#include <stddef.h>

struct log_entry { size_t root; long prev; };

static struct log_entry log_[1 << 20];
static size_t log_top = 0;

/* parent[i] < 0 at roots, holding -size. Returns 0 if already joined. */
static int unite_reversible(long *parent, size_t a, size_t b) {
    size_t ra = find(parent, a), rb = find(parent, b);   /* no compression */
    if (ra == rb) return 0;
    if (parent[ra] > parent[rb]) { size_t t = ra; ra = rb; rb = t; }

    log_[log_top++] = (struct log_entry){ ra, parent[ra] };
    log_[log_top++] = (struct log_entry){ rb, parent[rb] };
    parent[ra] += parent[rb];
    parent[rb] = (long)ra;
    return 1;
}

static void undo(long *parent) {
    struct log_entry e = log_[--log_top];
    parent[e.root] = e.prev;
    e = log_[--log_top];
    parent[e.root] = e.prev;
}

The find here must be the uncompressed loop. If it compressed, the log would not capture the rewrites, and undo would restore a structure that differs from the original — not necessarily incorrectly connected, but with a different shape, which breaks the invariant that the stack of states is a stack of identical snapshots.

Two entries per successful union is the minimum for this encoding. A unite that finds the roots already equal writes nothing and pushes nothing, so the log depth equals the number of merges on the current path, not the number of calls.

Why the height bound is enough

Without compression, union by size gives a height of at most ⌊log₂ n⌋. A find is therefore at most about 32 hops for n = 2³², and typically far fewer because the size rule keeps most trees shallow. The per-operation cost is O(log n) worst case, and the sequence cost is O(m log n) rather than O(m α(n)).

The trade is deliberate. Compression would buy a factor of log n / α(n), roughly eight at n = 2³², and would cost the ability to undo anything. For the offline algorithm the exchange rate is even worse than that, because the number of operations is inflated by the interval decomposition: each edge appears in O(log T) nodes of the time segment tree for T query times, so the total union count is O(E log T) and each costs O(log n).

The log’s memory is bounded by the depth of the walk, not by the number of operations. Along the path from the segment tree’s root to any leaf, each edge appears at most once, so the stack never holds more than one entry pair per edge — at most E merges. The buckets together hold O(E log T) edge copies, but the log only ever sees the copies stored on the current path. An entry is two 8-byte fields, 16 bytes, and a union pushes two entries, so a log sized for a million merges needs about 32 MB. Preallocating it from the edge count is the usual approach; growing it with realloc is safe only if the stack base is not captured in a pointer elsewhere, which is why the array above is indexed rather than walked with a moving pointer.

Segment tree over time

The offline algorithm rests on one observation: an edge that exists from time l to time r is present at every time in [l, r], and a segment tree over the time axis can store that edge at O(log T) nodes whose intervals partition [l, r]. A depth-first walk of the segment tree then visits each time exactly once, and the edges active at that time are exactly the edges stored on the path from the root to that leaf.

That is what makes rollback necessary. During the walk, entering a node applies the node’s edges; leaving it undoes them. The structure at any leaf therefore reflects exactly the edges whose intervals cover that time, and the answers are read off at the leaves.

struct edge { size_t u, v; };
struct bucket { struct edge *e; size_t count, cap; };

/* dfs over the time segment tree; `q` holds queries per leaf, `ans` the output. */
static void walk(int node, int lo, int hi, long *parent,
                 const struct bucket *bucket, const struct query *q,
                 int *ans) {
    size_t mark = log_top;
    for (size_t i = 0; i < bucket[node].count; i++)
        unite_reversible(parent, bucket[node].e[i].u, bucket[node].e[i].v);

    if (lo == hi) {
        ans[lo] = (find(parent, q[lo].u) == find(parent, q[lo].v));
    } else {
        int mid = lo + (hi - lo) / 2;
        walk(2 * node, lo, mid, parent, bucket, q, ans);
        walk(2 * node + 1, mid + 1, hi, parent, bucket, q, ans);
    }
    while (log_top > mark) undo(parent);   /* restore the entry state exactly */
}

The mark variable is the whole correctness argument. Every node restores the log to the depth it found, so the parent array at the start of each sibling subtree is byte-identical to what it was at the start of the first. Without the mark, a node that undid too far would corrupt its siblings.

Interval assignment and the edge lifetime problem

Building the buckets requires knowing each edge’s active interval. Two input shapes occur.

Explicit intervals. Each edge is given as (u, v, start, end) and the interval is inserted into the segment tree directly, at O(log T) nodes. Total storage is O(E log T).

Insertion and deletion events. Edges arrive and leave as events, and the interval is the gap between the matching pair. This requires a dictionary keyed by the edge, holding the insertion time; a deletion pops the entry and emits an interval. An edge deleted and reinserted produces two intervals, and an edge still present at the end produces an interval running to T. The dictionary is the fragile part: a deletion for an edge never inserted, or two deletions for one insertion, is an input error that produces silently wrong intervals rather than an exception.

The choice of T matters for the constant. T is the number of distinct times at which a query is asked, not the number of events, so a workload with many events and few queries gets a small tree. A workload with one query per event gets T = E, a segment tree with fewer than 2T nodes, and each edge’s interval is stored at O(log T) of them — so the bucket array holds O(E log E) edges, and the walk performs one union per stored entry.

A second limitation is concurrency. The log is a single global stack, and the mark discipline assumes one depth-first walk. Parallelising the walk requires either one structure per thread (which forfeits the shared merges) or a lock around the entire structure (which serialises it). Neither is a small change, and the sequential walk has the property that the union count is bounded by the bucket contents rather than by a per-level overhead, so the parallelism available is limited by the depth of the time tree rather than by E. In practice the leaf work has the most parallelism — each leaf answers its own queries against the structure its ancestors built — but the leaves are also the cheapest part.

The bound, and where it is not the right tool

Total work for E edges and T times over n vertices is O((E log T) log n) for the unions plus the cost of answering the queries at the leaves: two uncompressed finds per query, so O(Q log n) for Q queries in total. Storage is O(E log T) for the buckets and O(n) for the parent array and log.

The prefix-threshold case is worth separating from this one. Queries about a graph restricted to edges with weight below a threshold, where the answer at each query is a connectivity test on a prefix of the sorted edge list, are handled by sorting the edges, walking them once with a plain compressed structure, and answering each query at the point where the prefix ends. No rollback is needed, because the active set only grows. The rollback machinery earns its cost only when the active set is genuinely interval-shaped, so that two branches of the time tree hold different sets and neither contains the other.

Where the graph is a tree rather than a general graph, the union sequence has additional structure and a linear-time algorithm exists, as noted in The Inverse Ackermann Bound and Why It Is Effectively Constant. Where the merges carry payloads that must also be undone, the rollback log must record the payload writes as well, which is the same pattern extended to a second array.