library/query/OfflineDynamicConnectivity.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/query/OfflineDynamicConnectivity.hpp"

Depends on

Code

#include "library/datastructure/unionfind/UndoUnionFind.hpp"

class OfflineDynamicConnectivity {
    using edge = std::pair<int, int>;

    UnionFindUndo uf;
    int V, Q, segsz;
    std::vector<std::vector<edge>> seg;
    int comp;

    std::vector<std::pair<std::pair<int, int>, edge>> pend;
    std::map<edge, int> cnt, appear;

    OfflineDynamicConnectivity(int V, int Q) : uf(V), V(V), Q(Q), comp(V) {
        segsz = 1;
        while (segsz < Q)
            segsz <<= 1;
        seg.resize(2 * segsz - 1);
    }

    void insert(int idx, int s, int t) {
        auto e = std::minmax(s, t);
        if (cnt[e]++ == 0)
            appear[e] = idx;
    }

    void erase(int idx, int s, int t) {
        auto e = std::minmax(s, t);
        if (--cnt[e] == 0)
            pend.emplace_back(std::make_pair(appear[e], idx), e);
    }

    void add(int a, int b, const edge &e, int k, int l, int r) {
        if (r <= a || b <= l)
            return;
        if (a <= l && r <= b) {
            seg[k].emplace_back(e);
            return;
        }
        add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
        add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
    }

    void add(int a, int b, const edge &e) { add(a, b, e, 0, 0, segsz); }

    void build() {
        for (auto &p : cnt) {
            if (p.second > 0)
                pend.emplace_back(std::make_pair(appear[p.first], Q), p.first);
        }
        for (auto &s : pend) {
            add(s.first.first, s.first.second, s.second);
        }
    }

    int run(const function<void(int)> &f, int k = 0) {
        int add = 0;
        for (auto &e : seg[k]) {
            add += uf.unite(e.first, e.second);
        }
        comp -= add;
        if (k < segsz - 1) {
            run(f, 2 * k + 1);
            run(f, 2 * k + 2);
        } else if (k - (segsz - 1) < Q) {
            int query_index = k - (segsz - 1);
            f(query_index);
        }
        for (auto &e : seg[k]) {
            uf.undo();
        }
        comp += add;
    }
};

#line 1 "library/datastructure/unionfind/UndoUnionFind.hpp"
#include <cassert>
#include <stack>
#include <vector>

class UndoUnionFind {
    size_t n, num;
    std::vector<size_t> sz, parent;
    std::stack<std::pair<size_t, size_t>> sta;

  public:
    UndoUnionFind() = default;
    UndoUnionFind(size_t n) : n(n), num(n), sz(n, 1), parent(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    size_t leader(size_t x) const {
        assert(0 <= x and x < n);
        return (x == parent[x] ? x : leader(parent[x]));
    }

    bool same(size_t x, size_t y) const {
        assert(0 <= x and x < n and 0 <= y and y < n);
        return leader(x) == leader(y);
    }

    bool merge(size_t x, size_t y) {
        assert(0 <= x and x < n and 0 <= y and y < n);
        x = leader(x);
        y = leader(y);
        if (x == y)
            return false;
        if (sz[x] < sz[y])
            std::swap(x, y);
        sz[x] += sz[y];
        parent[y] = x;
        num--;
        sta.emplace(x, y);
        return true;
    }

    void undo() {
        if (!sta.size())
            return;
        auto [x, y] = sta.top();
        sta.pop();
        sz[x] -= sz[y];
        parent[y] = y;
        num++;
    }

    size_t size(const size_t x) const {
        assert(0 <= x and x < n);
        return sz[leader(x)];
    }

    size_t count() const { return num; }
};
#line 2 "library/query/OfflineDynamicConnectivity.hpp"

class OfflineDynamicConnectivity {
    using edge = std::pair<int, int>;

    UnionFindUndo uf;
    int V, Q, segsz;
    std::vector<std::vector<edge>> seg;
    int comp;

    std::vector<std::pair<std::pair<int, int>, edge>> pend;
    std::map<edge, int> cnt, appear;

    OfflineDynamicConnectivity(int V, int Q) : uf(V), V(V), Q(Q), comp(V) {
        segsz = 1;
        while (segsz < Q)
            segsz <<= 1;
        seg.resize(2 * segsz - 1);
    }

    void insert(int idx, int s, int t) {
        auto e = std::minmax(s, t);
        if (cnt[e]++ == 0)
            appear[e] = idx;
    }

    void erase(int idx, int s, int t) {
        auto e = std::minmax(s, t);
        if (--cnt[e] == 0)
            pend.emplace_back(std::make_pair(appear[e], idx), e);
    }

    void add(int a, int b, const edge &e, int k, int l, int r) {
        if (r <= a || b <= l)
            return;
        if (a <= l && r <= b) {
            seg[k].emplace_back(e);
            return;
        }
        add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
        add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
    }

    void add(int a, int b, const edge &e) { add(a, b, e, 0, 0, segsz); }

    void build() {
        for (auto &p : cnt) {
            if (p.second > 0)
                pend.emplace_back(std::make_pair(appear[p.first], Q), p.first);
        }
        for (auto &s : pend) {
            add(s.first.first, s.first.second, s.second);
        }
    }

    int run(const function<void(int)> &f, int k = 0) {
        int add = 0;
        for (auto &e : seg[k]) {
            add += uf.unite(e.first, e.second);
        }
        comp -= add;
        if (k < segsz - 1) {
            run(f, 2 * k + 1);
            run(f, 2 * k + 2);
        } else if (k - (segsz - 1) < Q) {
            int query_index = k - (segsz - 1);
            f(query_index);
        }
        for (auto &e : seg[k]) {
            uf.undo();
        }
        comp += add;
    }
};