Offline Dynamic Connectivity
(library/algorithm/offline_dynamic_connectivity.hpp)

• View this file on GitHub
• Last update: 2022-06-27 18:52:05+09:00
• Include: #include "library/algorithm/offline_dynamic_connectivity.hpp"

Offline Dynamic Connectivity

Dynamic Conectivity Problem をクエリ先読みにより $O(Q \log Q \log N)$ 時間で解く。時間軸を添字とした双対セグ木のノードに辺を乗せ、セグ木を dfs しながら Union Find を更新する。dfs の帰りがけで undo 操作をする必要があるので、Undo 可能 Union Find を用いる。

各辺は $O(\log Q)$ 個のノードに存在するので、Union Find の操作回数は $O(Q\log Q)$ 回である。Undo 可能 Union Find の各種操作の計算量は経路圧縮を行わないため $O(\log N)$ であるから、全体の計算量は $O(Q \log Q \log N)$ となる。

Depends on

• undo 可能 Union Find (library/datastructure/union_find/undo_union_find.hpp)

Code

#ifndef SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY
#define SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY

#include <map>
#include <tuple>

#include "library/datastructure/union_find/undo_union_find.hpp"

namespace suisen {
    struct OfflineDynamicConnectivity {
        OfflineDynamicConnectivity() : OfflineDynamicConnectivity(0) {}
        explicit OfflineDynamicConnectivity(int n) : _n(n) {}
        
        void add_query(int u, int v) {
            _active.emplace(std::minmax(u, v), _connectivity_queries.size());
        }
        void del_query(int u, int v) {
            auto it = _active.find(std::minmax(u, v));
            assert(it != _active.end());
            _active_range.emplace_back(u, v, it->second, _connectivity_queries.size());
            _active.erase(it);
        }
        void connectivity_query(int u, int v) {
            _connectivity_queries.emplace_back(u, v);
        }

        std::vector<bool> answer() {
            const int q = _connectivity_queries.size();
            for (auto it = _active.begin(); it != _active.end(); it = _active.erase(it)) {
                const auto &[u, v] = it->first;
                _active_range.emplace_back(u, v, it->second, q);
            }
            if (not q) return {};
            std::vector<std::vector<std::pair<int, int>>> seg(2 * q);
            for (auto [u, v, l, r] : _active_range) {
                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> ans(q);
            auto dfs = [&](auto dfs, int k) -> void {
                int update_counter = 0;
                for (const auto &[u, v] : seg[k]) update_counter += uf.merge(u, v);
                if (k >= q) {
                    const int query_id = k - q;
                    const auto &[u, v] = _connectivity_queries[query_id];
                    ans[query_id] = uf.same(u, v);
                } else {
                    dfs(dfs, 2 * k), dfs(dfs, 2 * k + 1);
                }
                while (update_counter --> 0) uf.undo();
            };
            dfs(dfs, 1);
            return ans;
        }
    private:
        int _n;
        std::multimap<std::pair<int, int>, int> _active;
        std::vector<std::tuple<int, int, int, int>> _active_range;
        std::vector<std::pair<int, int>> _connectivity_queries;
    };
} // namespace suisen


#endif // SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY

#line 1 "library/algorithm/offline_dynamic_connectivity.hpp"



#include <map>
#include <tuple>

#line 1 "library/datastructure/union_find/undo_union_find.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace suisen {
    struct UndoUnionFind {
        UndoUnionFind() : UndoUnionFind(0) {}
        explicit UndoUnionFind(int n) : _n(n), _dat(n, -1) {}

        int root(int x) const {
            assert(x < _n);
            return _dat[x] < 0 ? x : root(_dat[x]);
        }
        int operator[](int x) const {
            return root(x);
        }
        bool merge(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return false;
            if (_dat[x] > _dat[y]) std::swap(x, y);
            _history.emplace_back(x, std::exchange(_dat[x], _dat[x] + _dat[y]));
            _history.emplace_back(y, std::exchange(_dat[y], x));
            return true;
        }
        bool same(int x, int y) const {
            return root(x) == root(y);
        }
        int size(int x) const {
            return -_dat[root(x)];
        }
        auto groups() const {
            std::vector<std::vector<int>> res(_n);
            for (int i = 0; i < _n; ++i) res[root(i)].push_back(i);
            res.erase(std::remove_if(res.begin(), res.end(), [](const auto &g) { return g.empty(); }), res.end());
            return res;
        }
        void snapshot() {
            _history.clear();
        }
        void undo() {
            assert(_history.size());
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
        }
        void rollback() {
            while (_history.size()) undo();
        }
    protected:
        int _n;
        std::vector<int> _dat;
        std::vector<std::pair<int, int>> _history;
    };
} // namespace suisen



#line 8 "library/algorithm/offline_dynamic_connectivity.hpp"

namespace suisen {
    struct OfflineDynamicConnectivity {
        OfflineDynamicConnectivity() : OfflineDynamicConnectivity(0) {}
        explicit OfflineDynamicConnectivity(int n) : _n(n) {}
        
        void add_query(int u, int v) {
            _active.emplace(std::minmax(u, v), _connectivity_queries.size());
        }
        void del_query(int u, int v) {
            auto it = _active.find(std::minmax(u, v));
            assert(it != _active.end());
            _active_range.emplace_back(u, v, it->second, _connectivity_queries.size());
            _active.erase(it);
        }
        void connectivity_query(int u, int v) {
            _connectivity_queries.emplace_back(u, v);
        }

        std::vector<bool> answer() {
            const int q = _connectivity_queries.size();
            for (auto it = _active.begin(); it != _active.end(); it = _active.erase(it)) {
                const auto &[u, v] = it->first;
                _active_range.emplace_back(u, v, it->second, q);
            }
            if (not q) return {};
            std::vector<std::vector<std::pair<int, int>>> seg(2 * q);
            for (auto [u, v, l, r] : _active_range) {
                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> ans(q);
            auto dfs = [&](auto dfs, int k) -> void {
                int update_counter = 0;
                for (const auto &[u, v] : seg[k]) update_counter += uf.merge(u, v);
                if (k >= q) {
                    const int query_id = k - q;
                    const auto &[u, v] = _connectivity_queries[query_id];
                    ans[query_id] = uf.same(u, v);
                } else {
                    dfs(dfs, 2 * k), dfs(dfs, 2 * k + 1);
                }
                while (update_counter --> 0) uf.undo();
            };
            dfs(dfs, 1);
            return ans;
        }
    private:
        int _n;
        std::multimap<std::pair<int, int>, int> _active;
        std::vector<std::tuple<int, int, int, int>> _active_range;
        std::vector<std::pair<int, int>> _connectivity_queries;
    };
} // namespace suisen

Back to top page