undoable union find

ソースコード

 1#include <vector>
 2#include <stack>
 3using namespace std;
 4
 5// UndoableUnionFind
 6namespace titan23 {
 7
 8    class UndoableUnionFind {
 9      private:
10        int _n, _group_count;
11        vector<int> _parents;
12        stack<pair<int, int>> _history;
13
14      public:
15        UndoableUnionFind() {}
16        UndoableUnionFind(int n) :
17            _n(n), _group_count(n), _parents(n, -1) {}
18
19        void undo() {
20            auto [y, py] = _history.top();
21            _history.pop();
22            if (y == -1) return;
23            auto [x, px] = _history.top();
24            _history.pop();
25            ++_group_count;
26            _parents[y] = py;
27            _parents[x] = px;
28        }
29
30        int root(int x) const {
31            while (_parents[x] >= 0) {
32                x = _parents[x];
33            }
34            return x;
35        }
36
37        bool unite(int x, int y) {
38            x = root(x);
39            y = root(y);
40            if (x == y) {
41                _history.emplace(-1, -1);
42                return false;
43            }
44            if (_parents[x] > _parents[y]) swap(x, y);
45            _group_count -= 1;
46            _history.emplace(x, _parents[x]);
47            _history.emplace(y, _parents[y]);
48            _parents[x] += _parents[y];
49            _parents[y] = x;
50            return true;
51        }
52
53        int size(const int x) const {
54            return -_parents[root(x)];
55        }
56
57        bool same(const int x, const int y) const {
58            return root(x) == root(y);
59        }
60
61        int group_count() const {
62            return _group_count;
63        }
64    };
65} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/undoable_union_find.cpp