前書き
競技プログラミングのグラフ系問題において必須となるUnion-Find木について，ソースコードの解説と例題を用いた実装まで．
Union-Find木とは
Union-Find木とは，グループ分けを木構造で管理するデータ構造のこと．同じグループに属する＝同じ木に属するという木構造でグループ分けをする際，以下の二点を高速で行うことができるのがメリット．
・要素xと要素yが同じグループに属するかどうかを判定したい
→ 要素xの根と要素yの根が同じならば同じグループ，要素xの根と要素yの根が同じでないならば異なるグループにあることが分かる．
・要素xと要素yが同じグループに属する場合，要素xの属するグループと要素yの属するグループの併合する．
このスライドが非常に分かりやすい．
Union-Find木の原理とソースコード
以下のソースコードでUnion-Find木の原理を説明する．
vector<int> par：
par[a]=bとなると，「aの親がbである」という意味．
(例) ③-②-①という木の場合，③の親は②であるため，par[3]=2である．UnionFind(int N)：
1.で述べたparの定義に基づくと，par[i]=iのとき，「iの親はi」であるから，このiは木の根に相当する箇所である．
すなわちこの関数では，最初は全て根であるとして初期化する．int root(int x):
・データxが木の根の場合は，x（根）を返す．
・データxが木の根でない場合は，parで親を再帰的にたぐり，最終的に親のおおもと（根）を返す．
(例) ③-②-①という木でroot(3)の場合
ⅰ. ③の親は②であるため，par[3]=2である．root(2)を返す．
ⅱ. ②の親は①であるため，par[2]=1である．root(1)を返す．
ⅲ. ①は根であるため，1を返す．
すなわちこの関数は，xの根を返す関数であるvoid unite(int x, int y)：
xの根である所のrxとyの根である所のryが同じならば，そのまま．同じでないときは，xの根ryをyの根ryにつける．
すなわちこの関数は，根が同じでない(＝同じ木でない)二つの木を併合する関数である．bool same(int x, int y)：
2つのデータx,yが属する木が同じならtrueを返す関数である
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問題
この問題の解説はこちら.
・先ほどのスライドの[問題]
解答
#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問題
解答
#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
