AntInLoop

Disjoint Set (Weighted & Rollback DSU) Data Structure

A Disjoint Set (DSU) partitions elements into non-overlapping sets and extends cleanly to Weighted/Potential DSU (tracking relative offsets or parity) and Rollback DSU (supporting undo).

OperationComplexity
AccessO(alpha(n))
SearchO(alpha(n))
InsertionO(alpha(n))
DeletionO(log n) with rollback
SpaceO(n)

Interactive Visualizer · C++ / Python / Java / JS Code

Disjoint Set (Weighted & Rollback DSU)

Beyond basic connectivity (Union-Find), Disjoint Set structures generalize cleanly to two powerhouse competitive-programming variants:

1. Weighted / Potential DSU: Tracks a relative weight/parity diff[x] between x and parent[x]—answering dynamic bipartiteness ("are u and v enemies or friends?") and relative-difference constraints (val[v] - val[u] = w) in $O(\alpha(n))$!

2. Rollback DSU: Drops path compression (keeping only union by size, which guarantees height $\le \log_2 n$) and logs every merge on a stack so you can undo recent merges in $O(1)$!

At a Glance

| Variant | find / unite | Supports Undo? |

| :--- | :---: | :---: |

| Standard DSU (Path Compression + Size) | $O(\alpha(n))$ | No |

| Weighted / Potential DSU | $O(\alpha(n))$ | No |

| Rollback DSU (Size Only) | $O(\log n)$ | Yes ($O(1)$ per rollback) |

---

Practice Problems

Intermediate

1. Potential (Weighted) DSU: Check Relative Difference Constraints (val[v] - val[u] = w)

Process equations val[v] - val[u] = w online, detecting contradictions and answering val[b] - val[a] queries in $O(\alpha(n))$!

Approach: Maintain weight[x] = val[x] - val[parent[x]]. During path compression, accumulate weight[x] += weight[p[x]]. When merging roots ra and rb, set weight[rb] = weight[a] + w - weight[b].

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <numeric>
#include <vector>

struct PotentialDSU {
    std::vector<int> p;
    std::vector<long long> diff; // val[x] - val[p[x]]

    explicit PotentialDSU(int n) : p(n), diff(n, 0) {
        std::iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        if (p[x] == x) return x;
        int root = find(p[x]);
        diff[x] += diff[p[x]];
        return p[x] = root;
    }

    // Assert val[v] - val[u] == w; returns false on contradiction
    bool relate(int u, int v, long long w) {
        int ru = find(u), rv = find(v);
        if (ru == rv) return (diff[v] - diff[u]) == w;
        p[rv] = ru;
        diff[rv] = diff[u] + w - diff[v];
        return true;
    }

    long long queryDiff(int u, int v) { // val[v] - val[u]
        find(u); find(v);
        return diff[v] - diff[u];
    }
};

int main() {
    PotentialDSU dsu(4);
    std::cout << std::boolalpha
              << dsu.relate(0, 1, 5) << " "
              << dsu.relate(1, 2, 3) << " "
              << dsu.relate(0, 2, 9) << " " // contradicts 5 + 3 = 8 -> false
              << dsu.queryDiff(0, 2) << "\n"; // 8
    return 0;
}

</details>

2. Rollback DSU (With Snapshots & Undo)

Implement a Disjoint Set supporting unite(a, b), snapshot(), and rollback(snap) to revert merges!

Approach: Use union by size without path compression, pushing (childRoot, oldParentSize) onto a history stack on every real merge. Time: $O(\log n)$ per find/unite, $O(1)$ per undone merge.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

struct RollbackDSU {
    std::vector<int> p, sz;
    std::vector<std::pair<int, int>> history;
    int components;

    explicit RollbackDSU(int n) : p(n), sz(n, 1), components(n) {
        std::iota(p.begin(), p.end(), 0);
    }
    int find(int x) const { while (p[x] != x) x = p[x]; return x; }

    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) std::swap(a, b);
        history.push_back({b, sz[a]});
        p[b] = a;
        sz[a] += sz[b];
        --components;
        return true;
    }

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

    void rollback(size_t snap) {
        while (history.size() > snap) {
            auto [b, oldSzA] = history.back();
            history.pop_back();
            int a = p[b];
            p[b] = b;
            sz[a] = oldSzA;
            ++components;
        }
    }
};

int main() {
    RollbackDSU dsu(4);
    dsu.unite(0, 1);
    size_t snap = dsu.snapshot();
    dsu.unite(1, 2); dsu.unite(2, 3);
    std::cout << dsu.components << " "; // 1
    dsu.rollback(snap);
    std::cout << dsu.components << "\n"; // 3
    return 0;
}

</details>

---

Related Structures & Algorithms