union find advance

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4#include <stack>
  5#include <map>
  6#include <set>
  7using namespace std;
  8
  9// UnionFindAdvance
 10namespace titan23 {
 11
 12    class UnionFindAdvance {
 13      private:
 14        int n, group_numbers;
 15        vector<int> par;
 16        vector<vector<int>> G;
 17
 18      public:
 19        UnionFindAdvance() {}
 20        UnionFindAdvance(int n) : n(n), group_numbers(n), par(n, -1), G(n) {}
 21
 22        int root(int x) {
 23            int a = x, y;
 24            while (par[a] >= 0) a = par[a];
 25            while (par[x] >= 0) {
 26                y = x;
 27                x = par[x];
 28                par[y] = a;
 29            }
 30            return a;
 31        }
 32
 33        bool unite(int x, int y) {
 34            x = root(x);
 35            y = root(y);
 36            if (x == y) return false;
 37            --group_numbers;
 38            G[x].emplace_back(y);
 39            G[y].emplace_back(x);
 40            if (par[x] >= par[y]) swap(x, y);
 41            par[x] += par[y];
 42            par[y] = x;
 43            return true;
 44        }
 45
 46        int size(const int x) {
 47            return -par[root(x)];
 48        }
 49
 50        bool same(const int x, const int y) {
 51            return root(x) == root(y);
 52        }
 53
 54        set<int> members(const int x) const {
 55            set<int> seen;
 56            seen.emplace(x);
 57            stack<int> todo;
 58            todo.emplace(x);
 59            while (!todo.empty()) {
 60                int v = todo.top(); todo.pop();
 61                for (const int &x: G[v]) {
 62                    if (seen.find(x) != seen.end()) continue;
 63                    todo.emplace(x);
 64                    seen.emplace(x);
 65                }
 66            }
 67            return seen;
 68        }
 69
 70        vector<int> all_roots() const {
 71            vector<int> res;
 72            for (int i = 0; i < n; ++i) {
 73                if (par[i] < 0) res.emplace_back(i);
 74            }
 75            return res;
 76        }
 77
 78        int group_count() const {
 79            return group_numbers;
 80        }
 81
 82        void clear() {
 83            group_numbers = n;
 84            for (int i = 0; i < n; ++i) par[i] = -1;
 85            for (int i = 0; i < n; ++i) G[i].clear();
 86        }
 87
 88        map<int, vector<int>> all_group_members() {
 89            map<int, vector<int>> res;
 90            for (int i = 0; i < n; ++i) {
 91                res[root(i)].emplace_back(i);
 92            }
 93            return res;
 94        }
 95
 96        friend ostream& operator<<(ostream& os, titan23::UnionFindAdvance &uf) {
 97            map<int, vector<int>> group_members = uf.all_group_members();
 98            os << "<UnionFindAdvance>\n";
 99            for (auto &[key, val]: group_members) {
100                os << "  " << key << " : ";
101                for (const int &v : val) {
102                    os << v << ", ";
103                }
104                os << endl;
105            }
106            return os;
107        }
108    };
109}  // namespace titan23

仕様

Warning

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