union find

ソースコード

 1#include <iostream>
 2#include <vector>
 3#include <map>
 4#include <cassert>
 5using namespace std;
 6
 7// UnionFind
 8namespace titan23 {
 9
10    class UnionFind {
11      public:
12        int n, group_numbers;
13        vector<int> par;
14
15        UnionFind() {}
16        UnionFind(int n) : n(n), group_numbers(n), par(n, -1) {}
17
18        int root(int x) {
19            int a = x, y;
20            while (par[a] >= 0) a = par[a];
21            while (par[x] >= 0) {
22                y = x;
23                x = par[x];
24                par[y] = a;
25            }
26            return a;
27        }
28
29        bool unite(int x, int y) {
30            x = root(x);
31            y = root(y);
32            if (x == y) return false;
33            --group_numbers;
34            if (par[x] >= par[y]) swap(x, y);
35            par[x] += par[y];
36            par[y] = x;
37            return true;
38        }
39
40        int size(const int x) {
41            return -par[root(x)];
42        }
43
44        bool same(const int x, const int y) {
45            return root(x) == root(y);
46        }
47
48        vector<int> all_roots() const {
49            vector<int> res;
50            for (int i = 0; i < n; ++i) {
51                if (par[i] < 0) res.emplace_back(i);
52            }
53            return res;
54        }
55
56        map<int, vector<int>> all_group_members() {
57            map<int, vector<int>> res;
58            for (int i = 0; i < n; ++i) {
59                res[root(i)].emplace_back(i);
60            }
61            return res;
62        }
63
64        int group_count() const {
65            return group_numbers;
66        }
67
68        void clear() {
69            group_numbers = n;
70            std::fill(par.begin(), par.end(), -1);
71        }
72
73        friend ostream& operator<<(ostream& os, titan23::UnionFind &uf) {
74            map<int, vector<int>> group_members = uf.all_group_members();
75            os << "<UnionFind>\n";
76            for (auto &[key, val]: group_members) {
77                os << "  " << key << " : ";
78                for (const int &v : val) {
79                    os << v << ", ";
80                }
81            }
82            return os;
83        }
84    };
85}  // namespace titan23

仕様

Warning

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