UnionFind

1
UnionFind uf(要素数);

1
uf.merge(a,b);

1
uf.isSame(a,b);

1
uf.size(a);

1
uf.groups();

1
class UnionFind {
2
public:
3
  int n;
4
  vector<int> p;
5
  UnionFind(int _n) : n(_n), p(_n, -1) {}
6
  bool merge(int a, int b) {
7
    int x = root(a), y = root(b);
8
    if (x == y)
9
      return false;
10
    if (-p[x] < -p[y])
11
      swap(x, y);
12
    p[x] += p[y], p[y] = x;
13
    return true;
14
  }
15
  bool isSame(int a, int b) {
16
    return root(a) == root(b);
17
  }
18
  int root(int a) {
19
    if (p[a] < 0)
20
      return a;
21
    return p[a] = root(p[a]);
22
  }
23
  int size(int a) {
24
    return -p[root(a)];
25
  }
26
  vector<vector<int>> groups() {
27
    vector<int> buf(n), size(n);
28
    for (int i = 0; i < n; i++) {
29
      buf[i] = root(i);
30
      size[buf[i]]++;
31
    }
32
    vector<vector<int>> res(n);
33
    for (int i = 0; i < n; i++)
34
      res[i].reserve(size[i]);
35
    for (int i = 0; i < n; i++)
36
      res[buf[i]].push_back(i);
37
    res.erase(remove_if(res.begin(), res.end(), [&](const vector<int> &v) { return v.empty(); }), res.end());
38
    return res;
39
  }
40
};