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