Offline Dynamic Connectivity
(src/datastructure/OfflineDynamicConnectivity.hpp)

• View this file on GitHub
• Last update: 2024-05-21 23:41:26+09:00
• Include: #include "src/datastructure/OfflineDynamicConnectivity.hpp"

概要

辺を全くもたない $n$ 頂点の無向グラフに対し辺の追加削除及び 2 点が連結かの判定クエリが計 $q$ 個オフラインで与えられるときにこれを $\mathrm{O}(q \log q \log n)$ 時間で処理するデータ構造． 多重辺にも対応している．

メンバ関数	効果	時間計算量
add(u, v)	2 点 $u, v$ を結ぶ辺を 1 本追加する．	$\mathrm{O}(\log q)$
del(u, v)	2 点 $u, v$ を結ぶ辺を 1 本削除する．その際，辺が必ず存在していなくてはならない．	$\mathrm{O}(\log q)$
query(u, v)	その時点で 2 点 $u, v$ が連結かどうか判定する．	$\mathrm{O}(1)$
solve()	連結性判定クエリの結果を格納した配列を返す．	$\mathrm{O}(q \log q \log n)$

Links

• ちょっと変わったセグメント木の使い方 - ei1333の日記

問題例

• 東京工業大学プログラミングコンテスト2022 I - XOR Reachable
• AtCoder Beginner Contest 301 Ex - Difference of Distance

Depends on

• Union Find with Undo Operation (src/datastructure/UndoUnionFind.hpp)

Code

#pragma once
#include <algorithm>
#include <map>
#include <tuple>
#include <utility>
#include "UndoUnionFind.hpp"

struct OfflineDynamicConnectivity {
    OfflineDynamicConnectivity(int n) : n(n) {}

    void add(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        time.emplace(std::minmax(u, v), qs.size());
    }

    void del(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        auto it = time.find(std::minmax(u, v));
        assert(it != time.end());
        es.emplace_back(u, v, it->second, qs.size());
        time.erase(it);
    }

    void query(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        qs.emplace_back(u, v);
    }

    std::vector<bool> solve() {
        int q = qs.size();
        if (q == 0) return {};
        for (auto it = time.begin(); it != time.end(); it = time.erase(it)) {
            const auto& [u, v] = it->first;
            es.emplace_back(u, v, it->second, q);
        }
        std::vector<std::vector<std::pair<int, int>>> seg(2 * q);
        for (auto [u, v, l, r] : es) {
            for (l += q, r += q; l < r; l >>= 1, r >>= 1) {
                if (l & 1) seg[l++].emplace_back(u, v);
                if (r & 1) seg[--r].emplace_back(u, v);
            }
        }
        UndoUnionFind uf(n);
        std::vector<bool> res(q);
        auto dfs = [&](auto self, int k) -> void {
            for (const auto& [u, v] : seg[k]) uf.merge(u, v);
            if (k >= q) {
                const auto& [u, v] = qs[k - q];
                res[k - q] = uf.same(u, v);
            } else {
                self(self, k << 1);
                self(self, k << 1 | 1);
            }
            for (int i = 0; i < int(seg[k].size()); i++) uf.undo();
        };
        dfs(dfs, 1);
        return res;
    }

  private:
    int n;
    std::multimap<std::pair<int, int>, int> time;
    std::vector<std::pair<int, int>> qs;
    std::vector<std::tuple<int, int, int, int>> es;
};

#line 2 "src/datastructure/OfflineDynamicConnectivity.hpp"
#include <algorithm>
#include <map>
#include <tuple>
#include <utility>
#line 2 "src/datastructure/UndoUnionFind.hpp"
#include <cassert>
#include <stack>
#include <vector>

struct UndoUnionFind {
    UndoUnionFind() {}

    UndoUnionFind(int n) : n(n), data(n, -1) {}

    int find(int x) const {
        assert(0 <= x && x < n);
        return data[x] < 0 ? x : find(data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        x = find(x), y = find(y);
        history.emplace(x, data[x]);
        history.emplace(y, data[y]);
        if (x == y) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    bool same(int x, int y) const {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(x) == find(y);
    }

    int size(int x) const {
        assert(0 <= x && x < n);
        return -data[find(x)];
    }

    void undo() {
        assert(!history.empty());
        data[history.top().first] = history.top().second;
        history.pop();
        data[history.top().first] = history.top().second;
        history.pop();
    }

    void snapshot() {
        while (!history.empty()) history.pop();
    }

    void rollback() {
        while (!history.empty()) undo();
    }

    int operator[](int x) const { return find(x); }

  private:
    int n;
    std::vector<int> data;
    std::stack<std::pair<int, int>> history;
};
#line 7 "src/datastructure/OfflineDynamicConnectivity.hpp"

struct OfflineDynamicConnectivity {
    OfflineDynamicConnectivity(int n) : n(n) {}

    void add(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        time.emplace(std::minmax(u, v), qs.size());
    }

    void del(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        auto it = time.find(std::minmax(u, v));
        assert(it != time.end());
        es.emplace_back(u, v, it->second, qs.size());
        time.erase(it);
    }

    void query(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        qs.emplace_back(u, v);
    }

    std::vector<bool> solve() {
        int q = qs.size();
        if (q == 0) return {};
        for (auto it = time.begin(); it != time.end(); it = time.erase(it)) {
            const auto& [u, v] = it->first;
            es.emplace_back(u, v, it->second, q);
        }
        std::vector<std::vector<std::pair<int, int>>> seg(2 * q);
        for (auto [u, v, l, r] : es) {
            for (l += q, r += q; l < r; l >>= 1, r >>= 1) {
                if (l & 1) seg[l++].emplace_back(u, v);
                if (r & 1) seg[--r].emplace_back(u, v);
            }
        }
        UndoUnionFind uf(n);
        std::vector<bool> res(q);
        auto dfs = [&](auto self, int k) -> void {
            for (const auto& [u, v] : seg[k]) uf.merge(u, v);
            if (k >= q) {
                const auto& [u, v] = qs[k - q];
                res[k - q] = uf.same(u, v);
            } else {
                self(self, k << 1);
                self(self, k << 1 | 1);
            }
            for (int i = 0; i < int(seg[k].size()); i++) uf.undo();
        };
        dfs(dfs, 1);
        return res;
    }

  private:
    int n;
    std::multimap<std::pair<int, int>, int> time;
    std::vector<std::pair<int, int>> qs;
    std::vector<std::tuple<int, int, int, int>> es;
};

Back to top page