lib/include/clusters.hpp


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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <vector>
#include "graph.hpp"

class ClusterTree {
private:
  std::vector<signed> p;
  std::vector<unsigned> o;

public:
  std::vector<unsigned> c;

  ClusterTree(unsigned n) : p(n, -1), o(n, 1), c(n, 0) { c[0] = n; }

  unsigned findroot(unsigned i) {
    if (p[i] < 0)
      return i;
    else
      return p[i] = this->findroot(p[i]);
  }

  void join(unsigned i, unsigned j) {
    c[o[i] - 1]--;
    c[o[j] - 1]--;

    if (o[i] < o[j]) {
      p[i] = j;
      o[j] += o[i];
      c[o[j] - 1]++;
    } else {
      p[j] = i;
      o[i] += o[j];
      c[o[i] - 1]++;
    }
  }

  void add_bond(const graph::edge& b) {
    unsigned i = this->findroot(b.v[0]);
    unsigned j = this->findroot(b.v[1]);

    if (i != j) {
      this->join(i, j);
    }
  }

  bool same_component(unsigned v0, unsigned v1) {
    unsigned i = this->findroot(v0);
    unsigned j = this->findroot(v1);

    return i == j;
  }
};