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

• View this file on GitHub
• Last update: 2022-06-27 18:51:28+09:00
• Include: #include "library/datastructure/union_find/undo_union_find.hpp"

undo 可能 Union Find

経路圧縮を諦めることで undo 操作を可能にした Union Find。weighted union heuristic による集合の併合のみを行うので、各種操作の計算量は $O(\log N)$ である。

Required by

• Offline Dynamic Connectivity (library/algorithm/offline_dynamic_connectivity.hpp)
• 連結成分の可換モノイド和取得クエリがある場合の Offline Dynamic Connectivity (library/algorithm/offline_dynamic_connectivity_component_sum.hpp)
• 連結成分の可換モノイド和を取得できる undo 可能 Union Find (library/datastructure/union_find/undo_union_find_component_sum.hpp)

Verified with

• test/src/algorithm/offline_dynamic_connectivity_component_sum/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#ifndef SUISEN_UNDO_UNION_FIND
#define SUISEN_UNDO_UNION_FIND

#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


#endif // SUISEN_UNDO_UNION_FIND

#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

Back to top page