Help us understand the problem. What is going on with this article?

Union-Find木の解説と例題

More than 1 year has passed since last update.

前書き

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

ofutonfuton
初心者の備忘録的Qiita
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした