Union-Find木の解説と例題

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

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

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

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

[このスライド](https://atc001.contest.atcoder.jp/tasks/unionfind_a )が非常に分かりやすい．

#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問題](https://abc097.contest.atcoder.jp/tasks/arc097_b)

この問題の解説は[こちら](https://qiita.com/ofutonfuton/items/550c984f08e39a189ca6).

・先ほどのスライドの[[問題]](https://atc001.contest.atcoder.jp/tasks/unionfind_a)

**解答**

```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問題](https://arc032.contest.atcoder.jp/tasks/arc032_2)

**解答**

```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