Weighted DSU (Potentials/Parity) & Rollback DSU for Dynamic Connectivity Over Time

1. Weighted DSU: Path-Compressed Group Potentials

Suppose each edge $(u, v)$ imposes a constraint $\phi(u) - \phi(v) = w$ in an abelian group $(G, +)$ (or $\phi(u) \oplus \phi(v) = 1$ for 2-coloring / bipartiteness). In a Weighted DSU, every node $x$ stores $\text{diff}[x]$, defined as the group difference between $x$ and its immediate parent $\text{parent}[x]$:

2. Rollback DSU & Segment Tree Over Time (Offline Dynamic Connectivity)

Why must Rollback DSU disable path compression? A single find(x) with path compression can modify $O(\log N)$ parent pointers, and undoing all of them would require $O(\log N)$ space per query while losing the amortized bound anyway under repeated undo/redo cycles. Using Union by Size without path compression guarantees:

• Every find(x) is a read-only $O(\log N)$ walk up the tree.
• Every unite(a, b) mutates at most two array slots (parent[rb] = ra and size[ra] += size[rb]), which can be pushed onto a history stack and rolled back in strict $O(1)$ time!

To handle arbitrary edge additions and deletions over time steps $t \in [0, Q-1]$, each edge $e$ is active on one or more time intervals $[l, r]$. Inserting each interval into a Segment Tree over Time splits $[l, r]$ into $O(\log Q)$ segment tree nodes. A single DFS over the segment tree applies dsu.unite(u, v) upon entering a node and calls dsu.rollback(checkpoint) upon exiting!

Complexity Matrix

Production Implementation: Rollback DSU & Weighted Potential DSU

#include <vector>
#include <utility>

class RollbackDSU {
public:
    explicit RollbackDSU(int n) : p(n, -1), comps(n) {}

    int find(int x) const noexcept {
        while (p[x] >= 0) x = p[x];
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (p[a] > p[b]) std::swap(a, b); // p[a] is more negative (larger size)
        history.emplace_back(b, p[b]);
        p[a] += p[b];
        p[b] = a;
        --comps;
        return true;
    }

    size_t snapshot() const noexcept { return history.size(); }

    void rollback(size_t targetSize) noexcept {
        while (history.size() > targetSize) {
            auto [b, oldNegSizeB] = history.back();
            history.pop_back();
            int a = p[b];
            p[a] -= oldNegSizeB;
            p[b] = oldNegSizeB;
            ++comps;
        }
    }

    int components() const noexcept { return comps; }

private:
    std::vector<int> p;
    std::vector<std::pair<int, int>> history;
    int comps;
};

class WeightedDSU {
public:
    explicit WeightedDSU(int n) : parent(n, -1), diff(n, 0) {}

    // Returns (root, phi(x) - phi(root))
    std::pair<int, long long> find(int x) {
        if (parent[x] < 0) return {x, 0};
        auto [r, dParent] = find(parent[x]);
        parent[x] = r;
        diff[x] += dParent;
        return {r, diff[x]};
    }

    // Enforces phi(u) - phi(v) == w. Returns false if inconsistent with existing component!
    bool unite(int u, int v, long long w) {
        auto [ru, du] = find(u);
        auto [rv, dv] = find(v);
        if (ru == rv) return (du - dv) == w;
        if (parent[ru] > parent[rv]) {
            parent[rv] += parent[ru];
            parent[ru] = rv;
            diff[ru] = w + dv - du;
        } else {
            parent[ru] += parent[rv];
            parent[rv] = ru;
            diff[rv] = du - dv - w;
        }
        return true;
    }

private:
    std::vector<int> parent;
    std::vector<long long> diff;
};