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

#include <vector>

class PathCompressionDsu : public std::vector<int> {
public:
  explicit PathCompressionDsu(int n) : std::vector<int>(n, -1) {}

  int find(int u) {
    auto &U = operator[](u);
    if (U == -1) {
      return u;
    }
    if (U != u) {
      U = find(U);
    }
    return U;
  }

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