PKU演習問メモ(6/14)

No.	問題名	問題の種類および解法	難易度
2524	Ubiquitous Religions	Union find	★★☆☆☆

2524 Ubiquitous Religions

問題概要

n人の学生達がいくつかの異なる宗教を信じている。
今m個の"学生aと学生bの信じている宗教が同じ"という関係が与えられるとき、学生達の信じる宗教の数を求めよ。

解法

僕にとっての初union find.

Union findのデータ構造を使う。
iwi先生の資料が凄く解りやすいのでこちら参照。
http://d.hatena.ne.jp/iwiwi/20100328/1269790390

この問題では経路圧縮のみで計算時間は余裕。

ソースコード

int n,m,cs=0;
int u[50000]; bool v[50000];

int find(int x)
{
	if(u[x]==x)return x;
	else return u[x]=find(u[x]);
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y)u[x]=y;
}

int main()
{
	
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,n)u[i]=i,v[i]=0;
		rep(i,m)
		{
			int a,b; scanf("%d%d",&a,&b);
			merge(a-1,b-1);
		}
		
		int ans=0;
		rep(i,n)
		{
			int root=find(i);
			if(!v[root])ans++,v[root]=1;
		}
		
		printf("Case %d: %d\n",++cs,ans);
	}
	
	return 0;
}