LoginSignup
201

Union-Find木の解説と例題

Last updated at Posted at 2018-06-06

#前書き
 競技プログラミングのグラフ系問題において必須となる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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
201