Offline Dynamic Connectivity
(graph/offline_dynamic_connectivity.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/offline_dynamic_connectivity.hpp"

Description

グラフに対する以下のクエリをオフラインで処理する:

• 辺の追加
• 辺の削除
• 頂点の値の更新
• 2頂点が同一の連結成分に属するかの判定
• 連結成分の fold

Undo 可能 union find を用いることでこれらの操作を実現する．

空間計算量: $O(n + q\log q)$, $q$ はクエリ数

Operations

• OfflineDynamicConnectivity(int n)
  • グラフを頂点数 nで初期化する．頂点の値は単位元 $e$ で初期化される．
  • 時間計算量: $O(n)$
• OfflineDynamicConnectivity(vector<T> v)
  • グラフを頂点数 n = v.size()で初期化する．頂点の値は v で初期化される．
  • 時間計算量: $O(n)$
• void link(int u, int v)
  • 辺 $uv$ を追加する
• void cut(int u, int v)
  • 辺 $uv$ を削除する
• void update(int v, T x)
  • $a_v$ を $a_v \cdot x$ に更新する
• void same(int u, int v)
  • 頂点 $u,v$ が同一の連結成分に属するかどうか判定する
• void component_fold(int v)
  • 頂点 $v$ が属する連結成分の頂点の値を fold する
• vector<pair<bool, T>> run()
  • クエリを実行し， same と component_foldの結果を返す． (返り値は {same の結果, M::id()} または {false, component_fold の結果} の形式)
  • 時間計算量: $O(n + q\log q\log n)$

Depends on

• Undoable Union Find (data-structure/unionfind/undoable_union_find.hpp)

Verified with

• test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#pragma once
#include <algorithm>
#include <bit>
#include <cassert>
#include <map>
#include <tuple>
#include <utility>
#include <vector>

#include "../data-structure/unionfind/undoable_union_find.hpp"

template <typename M>
class OfflineDynamicConnectivity {
    using T = M::T;

   public:
    OfflineDynamicConnectivity() = default;
    explicit OfflineDynamicConnectivity(int n)
        : OfflineDynamicConnectivity(std::vector<T>(n, M::id())) {}
    explicit OfflineDynamicConnectivity(const std::vector<T>& v) : val(v) {}

    void link(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        open.emplace(edge, now);
    }

    void cut(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        auto it = open.find(edge);
        assert(it != open.end());
        closed.emplace_back(edge.first, edge.second, it->second, now);
        open.erase(it);
    }

    void update(int v, const T& x) {
        ++now;
        query_update.emplace_back(now, v, x);
    }

    void same(int u, int v) {
        ++now;
        query_same[now] = {u, v};
    }

    void component_fold(int v) {
        ++now;
        query_fold[now] = v;
    }

    std::vector<std::pair<bool, T>> run() {
        ++now;

        // cut edges
        for (auto [edge, s] : open) {
            closed.emplace_back(edge.first, edge.second, s, now);
        }

        // build a segment tree
        int size = std::bit_ceil((unsigned int)now);
        std::vector<std::vector<std::pair<int, int>>> edges(2 * size);
        std::vector<std::vector<std::pair<int, T>>> updates(2 * size);

        for (auto [u, v, s, t] : closed) {
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) edges[s++].emplace_back(u, v);
                if (t & 1) edges[--t].emplace_back(u, v);
            }
        }

        for (auto [s, v, x] : query_update) {
            int t = size;
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) updates[s++].emplace_back(v, x);
                if (t & 1) updates[--t].emplace_back(v, x);
            }
        }

        // handle queries
        UndoableUnionFind<M> uf(val);
        std::vector<std::pair<bool, T>> ret;

        auto dfs = [&](const auto& self, int k) -> void {
            for (auto [u, v] : edges[k]) {
                uf.unite(u, v);
            }
            for (auto [v, x] : updates[k]) {
                uf.update(v, x);
            }
            if (k < size) {
                self(self, 2 * k);
                self(self, 2 * k + 1);
            } else if (k < size + now) {
                if (query_same.contains(k - size)) {
                    auto [u, v] = query_same[k - size];
                    ret.emplace_back(uf.same(u, v), M::id());
                }
                if (query_fold.contains(k - size)) {
                    ret.emplace_back(false,
                                     uf.component_fold(query_fold[k - size]));
                }
            }
            for (int i = 0; i < (int)(edges[k].size() + updates[k].size());
                 ++i) {
                uf.undo();
            }
        };

        dfs(dfs, 1);
        return ret;
    }

   private:
    int now = 0;
    std::multimap<std::pair<int, int>, int> open;
    std::vector<std::tuple<int, int, int, int>> closed;
    std::vector<std::tuple<int, int, T>> query_update;
    std::map<int, std::pair<int, int>> query_same;
    std::map<int, int> query_fold;
    std::vector<T> val;
};

#line 2 "graph/offline_dynamic_connectivity.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <map>
#include <tuple>
#include <utility>
#include <vector>

#line 4 "data-structure/unionfind/undoable_union_find.hpp"
#include <stack>
#line 7 "data-structure/unionfind/undoable_union_find.hpp"

template <typename M>
class UndoableUnionFind {
    using T = M::T;

   public:
    UndoableUnionFind() = default;
    explicit UndoableUnionFind(int n)
        : UndoableUnionFind(std::vector<T>(n, M::id())) {}
    explicit UndoableUnionFind(const std::vector<T>& v)
        : data(v.size(), -1), val(v.begin(), v.end()) {}

    int find(int x) const {
        if (data[x] < 0) return x;
        return find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        history.emplace(y, data[y], val[y]);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        val[x] = M::op(val[x], val[y]);
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [x, dx, vx] = history.top();
            history.pop();
            if (x == -1) break;
            data[x] = dx;
            val[x] = vx;
        }
    }

    bool same(int x, int y) const { return find(x) == find(y); }

    int size(int x) const { return -data[find(x)]; }

    T component_fold(int x) const { return val[find(x)]; }

    void update(int x, const T& v) {
        x = find(x);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        val[x] = M::op(val[x], v);
    }

   private:
    std::vector<int> data;
    std::vector<T> val;
    std::stack<std::tuple<int, int, T>> history;
};
#line 11 "graph/offline_dynamic_connectivity.hpp"

template <typename M>
class OfflineDynamicConnectivity {
    using T = M::T;

   public:
    OfflineDynamicConnectivity() = default;
    explicit OfflineDynamicConnectivity(int n)
        : OfflineDynamicConnectivity(std::vector<T>(n, M::id())) {}
    explicit OfflineDynamicConnectivity(const std::vector<T>& v) : val(v) {}

    void link(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        open.emplace(edge, now);
    }

    void cut(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        auto it = open.find(edge);
        assert(it != open.end());
        closed.emplace_back(edge.first, edge.second, it->second, now);
        open.erase(it);
    }

    void update(int v, const T& x) {
        ++now;
        query_update.emplace_back(now, v, x);
    }

    void same(int u, int v) {
        ++now;
        query_same[now] = {u, v};
    }

    void component_fold(int v) {
        ++now;
        query_fold[now] = v;
    }

    std::vector<std::pair<bool, T>> run() {
        ++now;

        // cut edges
        for (auto [edge, s] : open) {
            closed.emplace_back(edge.first, edge.second, s, now);
        }

        // build a segment tree
        int size = std::bit_ceil((unsigned int)now);
        std::vector<std::vector<std::pair<int, int>>> edges(2 * size);
        std::vector<std::vector<std::pair<int, T>>> updates(2 * size);

        for (auto [u, v, s, t] : closed) {
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) edges[s++].emplace_back(u, v);
                if (t & 1) edges[--t].emplace_back(u, v);
            }
        }

        for (auto [s, v, x] : query_update) {
            int t = size;
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) updates[s++].emplace_back(v, x);
                if (t & 1) updates[--t].emplace_back(v, x);
            }
        }

        // handle queries
        UndoableUnionFind<M> uf(val);
        std::vector<std::pair<bool, T>> ret;

        auto dfs = [&](const auto& self, int k) -> void {
            for (auto [u, v] : edges[k]) {
                uf.unite(u, v);
            }
            for (auto [v, x] : updates[k]) {
                uf.update(v, x);
            }
            if (k < size) {
                self(self, 2 * k);
                self(self, 2 * k + 1);
            } else if (k < size + now) {
                if (query_same.contains(k - size)) {
                    auto [u, v] = query_same[k - size];
                    ret.emplace_back(uf.same(u, v), M::id());
                }
                if (query_fold.contains(k - size)) {
                    ret.emplace_back(false,
                                     uf.component_fold(query_fold[k - size]));
                }
            }
            for (int i = 0; i < (int)(edges[k].size() + updates[k].size());
                 ++i) {
                uf.undo();
            }
        };

        dfs(dfs, 1);
        return ret;
    }

   private:
    int now = 0;
    std::multimap<std::pair<int, int>, int> open;
    std::vector<std::tuple<int, int, int, int>> closed;
    std::vector<std::tuple<int, int, T>> query_update;
    std::map<int, std::pair<int, int>> query_same;
    std::map<int, int> query_fold;
    std::vector<T> val;
};

Back to top page