WeightedUnionFind

用途

UnionFindに重みを持たせて要素間の距離も管理できるようにしたもの.

計算量

$ O(\alpha(n)) $, $\alpha$はAckermann関数の逆関数

使い方

宣言

1
WeightedUnionFind<距離を表すclass> wuf(要素数);

クエリ

マージ

1
uf.merge(a,b,w);

aが属する集合と,bが属する集合をbの重み-aの重み = w、つまりaよりbの方がw重みがあるようにマージする.

同一の集合か判定

1
wuf.isSame(a,b);

a,bが同一の集合に属しているか判定する

集合サイズ

1
wuf.size(a);

aが属する集合の濃度を返す

重みの差

1
wuf.diff(a,b);

でbの重み-aの重みを得る.

実装

 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
template <class T>
class WeightedUnionFind {
public:
  WeightedUnionFind(int n) : parents(n, -1), weights(n, 0) {}
  int find(int i) {
    if (parents[i] < 0)
      return i;
    weights[i] += weights[parents[i]];
    return parents[i] = find(parents[i]);
  }
  void merge(int a, int b, T w) {
    w += weight(a) - weight(b);
    a = find(a), b = find(b);
    if (a != b) {
      if (-parents[a] < -parents[b]) {
        swap(a, b);
        w = -w;
      }
      parents[a] += parents[b];
      parents[b] = a;
      weights[b] = w;
    }
  }
  T diff(int a, int b) {
    return weight(b) - weight(a);
  }
  bool connected(int a, int b) {
    return find(a) == find(b);
  }
  int size(int i) {
    return -parents[find(i)];
  }
private:
  vector<int> parents;
  vector<T> weights;
  T weight(int i) {
    find(i);
    return weights[i];
  }
};

Verify

//TODO