path_compression_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

#include <numeric>
#include <vector>

class PathCompressionDsu {
  std::vector<int> parent;

public:
  explicit PathCompressionDsu(int n) : parent(n) {
    std::iota(parent.begin(), parent.end(), 0);
  }

  int find(int u) {
    if (parent[u] != u) {
      parent[u] = find(parent[u]);
    }
    return parent[u];
  }

  bool merge(int a, int b) {
    if (find(a) == find(b)) {
      return false;
    }
    parent[find(a)] = find(b);
    return true;
  }
};