自己流union-findの使い方

この記事では自分の愛用しているデータ構造であるunion-find木の自分のつかいかたについて書きます。
あくまで「自分の」使い方なのでもっといい使い方があるかもしれません。

この記事では、union-find木がどういうデータ構造かは知っているものとして話を進めます。

1.最小全域木

とりあえず一般的に一番union-find木が使われるシチュエーションのはず。
みんな大好きクラスカル法です。多分これについてはいうことはないので割愛します。プリムとかいうアルゴリズムでもできるらしいし。(使ったことない)

2.本当にunion-findが想定解の場合

50問に1問くらいの割合で(これは体感なのでどれくらいかはわからない)、本当にunion-find木が想定解っぽくて、かつ最小全域木問題ではないような問題があります。大体の人がUF木つかうのはここまでだと思っている。

http://www.codeforces.com/problemset/problem/217/A
これとか。簡単。

http://poj.org/problem?id=1291
ちょっと変わった問題だけどこれは面白い。良問。

http://poj.org/problem?id=2985
他のデータ構造と組み合わせて使うこともあります。

これらの問題に共通して言えることは、「集合を適当な順序でくっつけていって、連結成分について何か聞かれるので答えてください」ということです。このような問題の場合、union-findは「適当な順序で」集合を併合していけるという点で強いです(集合に要素を1個ずつ追加していくんだったら別にvectorかなにかをもっておけば事足りる)。

実際このような問題はそんなに多くなくて、setとかsegtreeを使う問題のほうが多い印象があります。ここまでは普通の人の使い方です。

3.連結成分の検出

実はunion-findはグラフに対して、「連結成分はいくつありますか」とか「各連結成分ごとに何かをする」という作業に強いです。連結成分の検出は幅優先探索をすればできますが、バグりやすい上にデバッグしにくく、また問題ごとに形が変わるのでライブラリがあればunion-find木を使うほうが楽です。オーダーもα(n)倍になるだけだし実際定数くらいです。

以下にグリッドグラフ上で連結成分を全部検出するコードを示します。ここでは周囲8方向を連結だとみなします。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define LIMIT 252
typedef pair<int,int>pii;
pii par[LIMIT][LIMIT];
int ran[LIMIT][LIMIT];
int ren[LIMIT][LIMIT];
void init()
{
	for(int i=0;i<LIMIT;i++)
	{
		for(int j=0;j<LIMIT;j++)
		{
			par[i][j]=make_pair(i,j);
			ran[i][j]=0;
			ren[i][j]=1;
		}
	}
}
pii find(pii a)
{
	if(par[a.first][a.second]==a)
	{
		return a;
	}
	else
	{
		return par[a.first][a.second]=find(par[a.first][a.second]);
	}
}
void unite(pii a,pii b)
{
	a=find(a);
	b=find(b);
	if(a==b)
	{
		return;
	}
	if(ran[a.first][a.second]>ran[b.first][b.second])
	{
		par[b.first][b.second]=a;
		ren[a.first][a.second]+=ren[b.first][b.second];
	}
	else
	{
		par[a.first][a.second]=b;
		ren[b.first][b.second]+=ren[a.first][a.second];
	}
	if(ran[a.first][a.second]==ran[b.first][b.second])
	{
		ran[b.first][b.second]++;
	}
}
int map[252][252];
int main()
{
	init();
	int mx,my;
	scanf("%d%d",&mx,&my);
	for(int i=0;i<252;i++)
	{
		for(int j=0;j<252;j++)
		{
			map[i][j]=0;
　　　　	}
	}
	for(int i=0;i<mx;i++)
	{
		for(int j=0;j<my;j++)
		{
			char zan;
			scanf(" %c",&zan);
			if(zan=='1')
			{
				if(map[i][j]==1)
				{
					unite(make_pair(i,j),make_pair(i+1,j+1));
				}
				if(map[i][j+1]==1)
				{
					unite(make_pair(i,j+1),make_pair(i+1,j+1));
				}
				if(map[i][j+2]==1)
				{
					unite(make_pair(i,j+2),make_pair(i+1,j+1));
				}
				if(map[i+1][j]==1)
				{
					unite(make_pair(i+1,j),make_pair(i+1,j+1));
				}
				map[i+1][j+1]=1;
			}
		}
	}
}

蟻本と違うのは、ren配列に連結成分の大きさが入っていることです。
連結成分の大きさを見たい時には、そこでfindして出てきた結果をren配列に食わせると見えます。

あと、このようにuniteを4方向ぶん実装すればいいようになっています。これは周囲4方向をつながっているとみなすなら2方向でよくなって楽です。
また、入力と一緒に処理できるのもうれしいです。

とりあえずunion-find木では、このように、幅優先探索をさぼることができます。また、「各連結成分で一番上にあるもの」とか「各連結成分内で一番書いてある数字が大きいもの」とかも配列を追加してunite関数をいじれば簡単に取り出せます。

以下問題例

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569
イルミネーション。連結成分だけが欲しいのでunion-findでいいです。

http://arc006.contest.atcoder.jp/tasks/arc006_4
この方法でさぼれます。

http://codeforces.com/contest/11/problem/C
上のと似てる。

注意すべきなのは、同じ幅優先探索でも、「最短経路を求めるタイプのものはできない」ということです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166
例えばこれ。入力の形式的にunion-findしたくなるけどできない。

あと、切れません。切れません。大切なことなので二回言いました。

4.link-cut tree
切れるらしい。こわい。知らない。