Union Find Tree

導入

union find treeはグループ分けを高速に管理するデータ構造です。
計算量は $O(α(n))$ で、これは $O(\log{n})$ と比較にならないほど超高速です。
どれくらい早いかというと競プロで用いるようなnの範囲では4を超えることがないでしょう。
$10^{1000}$ とかいっても余裕で4以下です。

例えば、次のような状況を考えてください。

10人の人がいる
最初は全員バラバラのグループ
「aさんとbさんを同じグループにする」という操作が何度も来る
「cさんとdさんは同じグループですか？」という質問に答えたい

この問題を解こうとなると以下のようにしてグループ分けをしたくなります。

union find treeでは、これを以下のように木で表現します。

例えばbの親を聞かれたらa、dの親を聞かれたらcのように答えるようにすることで、根が同じ=同じ木(グループ)に属すると判別できるわけです。

必要な要素の構築

初期化

では、このデータ構造に必要な機能を上記の例を参考にして考えてみましょう。
まずは木の作成をする必要がありますよね。
ノードの番号を与えるとその親ノードを返すような配列を宣言します。
配列名はなんでもいいですが、私はparentからとってparを使用しています。
初めは全てのノードを根とします。

void init(int x){
  for(int i=0;i<n;i++) par[i] = i;
}

findRoot

次にノードを与えるとその根を返すfindRootを作成します。
先程のこの画像の場合findRoot[b] = a、findRoot[a] = aとなります。

今見ているノードが根であるときpar[x] = xとなるので、こうなるまで再起的にループを回します。

int findRoot(int x){
  if(par[x] = x) return x; //親ノードが自分自身 = 今見ているノード(x)は根
  return findRoot(par[x]); //今見ているノード(x)の親ノード(par[x])を見る
}

same

次に特定のノード同士が同じ木(グループ)に属しているのか判定する関数sameを作ります。
これは特に解説はいらないでしょう。

bool same(int x, int y){
  return findRoot(x) == findRoot(y);
}

unite

最後に木(グループ)同士の結合をするuniteを作ります。
xとyを同じグループに結合する処理を与えられた時の処理は以下の2パターンに分けられます。

xとyが既に同じ木(グループ)に属している

xとyは別の木(グループ)に属している

1の場合は既に同じグループであるため、なにもする必要がないです。
2の場合はどちらかの木をもう片方の木に結合してやればいいですね。

bとcを結合しろと言われれば、こんな感じになります。

→

次の高速化の章で詳しく触れますがひとまず愚直に実装します。

void unite(int x, int y){
  x = findRoot[x];
  y = findRoot[y];
  if(x == y) return; //1の場合
  par[x] = y; //2の場合　par[y] = xでもいいです
}

高速化

さて、これで必要な要素が全て揃いました。しかしまだ懸念点があります。
現状では木が以下のような縦長になってしまう可能性があります。

これでは例えばfindRoot(f)をしたときにn回のループが必要となってしまいます。
このような問題を解決するために、一般に以下のような工夫をします。

経路圧縮

木の高さが低くなるように繋げる(ランクを低くする)

それぞれ見ていきましょう。

1.経路圧縮

例えば先程のように左側の画像のような状態でfindRoot(f)を実行すると、ノードb,c,d,e,fの根がaであることが処理中に判明します。
よって、右側の画像のようにパスを繋ぎ直してあげることで経路を圧縮できます。

→

これを下にfindRootを修正しましょう。

ここをクリックして修正前の`findRoot`を確認する

int findRoot(int x){
  if(par[x] = x) return x; //親ノードが自分自身 = 今見ているノード(x)は根
  return findRoot(par[x]); //今見ているノード(x)の親ノード(par[x])を見る
}

int findRoot(int x){
  //今見ているノードが根ではないならば, 親を根に付け替える
  if(par[x] != x) par[x] = findRoot(par[x]);
  //根まで到達したら根自身のノード番号を返す
  return par[x];
}

2.ランクを低くする

どうすればランクを低くできるでしょうか。
よくあるやり方としてはランクの低い方の木の根をランクの高い方の木の根に繋ぐ、です。

以下の画像ではランク2の木をランク3の木に結合しています。

→

では、ランクが上がる時というのはどういうときでしょうか。
複雑な場合分けが必要に感じるかもしれませんが、if文一個で完結します。
なぜならランクが上がるのは結合しようとしている木同士のランクが同じときだけだからです。
ランクに差がある場合、それは最小でも1なので小さい方の木を大きい方の木に結合したとてランクは変わらないわけです。というよりそのノードは根ではなくなるため参照されること自体なくなりますね。
uniteを修正します。

ここをクリックして修正前の`unite`を確認する

void unite(int x, int y){
  x = findRoot[x];
  y = findRoot[y];
  if(x == y) return; //1の場合
  par[x] = y; //2の場合　par[y] = xでもいいです
}

void unite(int x, int y){
  x = findRoot[x];
  y = findRoot[y];
  if(x == y) return;
  if(rank[x] < rank[y]) swap(x,y);
  par[y] = x;
  if(rank[x] == rank[y]) rank[x]++;
  return;
}

完成系

struct UnionFind {
  vector<int> par, rank;
  UnionFind(int n) : par(n), rank(n, 0){
    for(int i=0;i<n;i++) par[i]=i;
  }
  int findRoot(int x){
    if(par[x]!=x) par[x]=findRoot(par[x]);
    return par[x];
  }
  bool same(int x, int y){
    return findRoot(x)==findRoot(y);
  }
  void unite(int x, int y){
    x=findRoot(x);
    y=findRoot(y);
    if(x==y) return;
    if(rank[x]<rank[y]) swap(x,y);
    par[y]=x;
    if(rank[x]==rank[y]) rank[x]++;
  }
};

int main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    uf.unite(u,v);
  }
}

その他の例題

最後に

Union Find Treeは頻出ですので習得してみてください。
拡張性も高いですが苦手な場面(辺の削除や有向グラフの到達可能性など)もあります。その辺はやっていくうちにわかってくるでしょう。