Union-Find木の解説と例題

#前書き
　競技プログラミングのグラフ系問題において必須となるUnion-Find木について，ソースコードの解説と例題を用いた実装まで．

#Union-Find木とは
　Union-Find木とは，グループ分けを木構造で管理するデータ構造のこと．同じグループに属する＝同じ木に属するという木構造でグループ分けをする際，以下の二点を高速で行うことができるのがメリット．

・要素xと要素yが同じグループに属するかどうかを判定したい
　→ 要素xの根と要素yの根が同じならば同じグループ，要素xの根と要素yの根が同じでないならば異なるグループにあることが分かる．

・要素xと要素yが同じグループに属する場合，要素xの属するグループと要素yの属するグループの併合する．

このスライドが非常に分かりやすい．

#Union-Find木の原理とソースコード

　以下のソースコードでUnion-Find木の原理を説明する．

1. vector<int> par：
   par[a]=bとなると，「aの親がbである」という意味．
   (例) ③-②-①という木の場合，③の親は②であるため，par[3]=2である．

2. UnionFind(int N)：
   1.で述べたparの定義に基づくと，par[i]=iのとき，「iの親はi」であるから，このiは木の根に相当する箇所である．
   すなわちこの関数では，最初は全て根であるとして初期化する．

3. int root(int x):
   ・データxが木の根の場合は，x（根）を返す．
   ・データxが木の根でない場合は，parで親を再帰的にたぐり，最終的に親のおおもと（根）を返す．
   (例) ③-②-①という木でroot(3)の場合
   ⅰ. ③の親は②であるため，par[3]=2である．root(2)を返す．
   ⅱ. ②の親は①であるため，par[2]=1である．root(1)を返す．
   ⅲ. ①は根であるため，1を返す．
   すなわちこの関数は，xの根を返す関数である

4. void unite(int x, int y)：
   xの根である所のrxとyの根である所のryが同じならば，そのまま．同じでないときは，xの根rxをyの根ryにつける．
   すなわちこの関数は，根が同じでない(＝同じ木でない)二つの木を併合する関数である．

5. bool same(int x, int y)：
   2つのデータx, yが属する木が同じならtrueを返す関数である

UnionTree.cpp

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
    
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

#例題
・AtCoder Beginner Contest 097 D問題

この問題の解説はこちら.

・先ほどのスライドの[問題]

解答

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
    
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    
    UnionFind tree(N);
    
    for(int i = 0; i < Q; i++) {
        int p, x, y;
        cin >> p >> x >> y;
        if(p==0){
            tree.unite(x, y); // xの木とyの木を併合する
        }else{
            if(tree.same(x, y)){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }
    
    return 0;
}

・AtCoder Regular Contest 032 D問題

解答

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
    
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    
    UnionFind tree(N);
    
    for(int i = 0; i < M; i++) {
        int  x, y;
        cin >> x >> y;
        tree.unite(x-1, y-1); // xの木とyの木を併合する
    }
    
    int cnt=0;
    for(int i=0;i<N;i++){
        if(!tree.same(0,i)){
            tree.unite(0, i);
            cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

#あとがき
Union-Find木，場合によっては深さ優先探索の上位互換感がある．
#参考文献
http://pakapa104.hatenablog.com/entry/2016/02/04/233326#f-450e3664