学步园

题意：给出一些数对，表示这两个人有相同的宗教信仰，现在要求人们信仰的宗教最多有多少种。
题解：并查集。

#include <cstdio>
#include <memory>

int father[50001],r[50001];
int m,n,res;

void make_set ()
{
	for ( int i = 1; i <= n; i++ )
		father[i] = i;
	memset(r,0,sizeof(r));
}

int find_set ( int a )
{
	if ( a != father[a] )
		father[a] = find_set(father[a]);
	return father[a];
}

void Union ( int a, int b )
{
	int ta = find_set(a);
	int tb = find_set(b);
    if ( ta == tb ) return;
	res--;  
	if ( r[ta] > r[tb] )
		father[tb] = ta;
	else
		father[ta] = tb;
	if ( r[ta] == r[tb] )
		r[tb]++;
}

int main()
{
	int i,a,b,cnt=0;
	while ( scanf("%d%d",&n,&m) && (m+n) )
	{
	    ++cnt; res = n;
		make_set();
		for ( i = 0; i < m; ++i )
		{
			scanf("%d%d",&a,&b);
			Union(a,b);
		}
		printf("%s %d%s %d\n", "Case",cnt,":",res);
	}
	return 0;
}