Union-Find木について

　お久しぶりです。最近ブログ書いてませんでしたね。前から記事にしておきかった「Union-Find木」についてを書いていこうと思います。

（自分がUnion-Find木に出会ったのは、半年前でした......。）

「Union-Find木」とは何か？

　Union-Find木とは”グループ分けを管理するデータ構造”のことをいいます。ある要素と要素が同じグループに属するかを判定したり、同じグループに結合できたりとします。（ここで注意なのは、結合はできても分割はできないということです。)

　実際にデータ構造を見ながら、内容を紹介していこうと思います。

（半年前のことで忘れたのですが、データ構造は他の方のコードを参考にさせていただきました。コードはC++です。構造体の使い方については他の文献をご参照ください。）

#include<vector>

struct UnionFind{
	std::vector<int> par;
        /*xの親はpar[x].
        x自身が親ならpar[x]<0で、-par[x]がその集合のサイズ.*/
	
	UnionFind(int n):par(n,-1){}//コンストラクタ.
	
	void reset(int n){par.assign(n,-1);}
	int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
        //再帰.
	int size(int x){return -par[root(x)];}
	bool unite(int x,int y){
		x=root(x);
		y=root(y);
		if(x==y) return false;//do nothing.
		if(size(x)<size(y)) swap(x,y);//merge technique.
		par[x]+=par[y];
		par[y]=x;
		return true;
	}
};

• コンストラクタ UnionFind(int n)

　まずは宣言について。引数nの数の分の要素数の配列parを作ります。要素はすべて-1で初期化します。

　グループにはそれぞれ1つの”親”とその”子”に分かれます。ここでは親の要素の値を負の数、子の要素の値は親の番号としています。つまり「par[x]<0のとき、xは親。par[x]>=0ならxは子で、その親はpar[x]である」ということです。

　また、親の負の値の絶対値はグループ内の要素の数を示します。親の番号とグループの大きさをそれぞれ示す配列を2つ用いる方法もありますが、ここでは負の数を利用することで1つの配列で表現しています。詳しいことはあとで記します。

• 親の判定 root(int x)

　要素xの親の番号を返します。この関数では再帰を利用しています。

• グループの大きさの判定 size(int x)

　 要素xが所属するグループに含まれる要素の数を返します。root関数を用いてxの親を調べ、その要素の値の絶対値を出しています。（親の値の絶対値はグループの大きさでしたね。）

• 結合 unite(int x, int y)

　要素xが含まれるグループと要素yが含まれるグループを結合します。

　まずx, yにroot関数を用いて、それぞれの親の番号を代入します。ここで番号が同じならばここで終了します。番号が異なっているならば、y側のグループがx側のグループに結合すると考えると、par[x]+=par[y]でグループのサイズを足し合わせ、par[y]=xで新しい親を設定します。

　以上がUnion-Find木の構造体の説明でした。次の記事で実際にこのUnion-Find木を使って解ける問題をみていきたいと思います。（執筆中.）

参考文献

　この記事を書くにあたって、以下の書籍を参考にさせていただきました。

-『プログラミングコンテストチャレンジブック　第2版』秋葉拓哉、岩田陽一、北川宜稔 著、マイナビ出版（2012年）