dsu.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <vector>

class Dsu {
public:
  explicit Dsu(int n) : node(n) {
    for (int i = 0; i < n; i++) {
      node[i] = {i, 0};
    }
  }

  int find(int u) {
    while (node[u].p != u) {
      u = node[u].p = node[node[u].p].p;
    }
    return u;
  }

  bool merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) {
      return false;
    }
    if (node[a].r < node[b].r) {
      std::swap(a, b);
    }
    node[b].p = a;
    node[a].r += node[a].r == node[b].r;
    return true;
  }

private:
  struct Node {
    int p, r;
  };

  std::vector<Node> node;
};