Union Find

説明

Union Find は互いに素な集合を扱うための道具である．Union Find を用いると以下の操作を高速に行うことができる．

• union_set(x,y): x が入っている集合と y が入っている集合を併合する．
• find_set(x,y): x と y が同じ集合に入っているかを判定する．
• make_set(x): x のみが入る集合 {x} を作る．

アルゴリズムは次の考え方による．集合を多分木で管理し，木の根を集合の代表元とみなす．集合の併合は木の併合，二つの要素が同じ集合に入るかどうかは代表元が等しいかどうかの比較で行う．

これらの走査を単純な木で行った場合，検索や併合に最悪 O(n) かかってしまう．そこで平衡操作を取る．具体的には木の要素を手繰ったとき，それらの親ポインタをすべて根に張り替える．このときの計算量を見積もるのは複雑だが，ならし解析によって O(A(n)) となることが知られている．ここで A はアッカーマン関数の逆関数で，2^65536 ≦ A(5) なる極めてゆっくりと増加する関数である．

使い方

以下の実装では集合の要素となるのは上界の分かっている整数に限られている．これは，集合の要素に相当する頂点を直ちに得るための施策である．

union_set(x,y)

x が入っている集合と y が入っている集合を併合する．

find_set(x,y)

x と y が同じ集合に入っているかどうかを判定する．

make_set(x)

x のみが入る集合 {x} を作る．

計算量

• union_set, find_set: ならしコストの意味で O(A(n))
• make_set: O(1)

ソースコード

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

Verified

• UVA 793 (Network Connections), 2809 MS