2833.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int h[100005],f[100005];
int findhead(int t)
{
	if(h[t]==t)return t;
	else
	{
		h[t]=findhead(h[t]);
		return h[t];
	}
}


int main()
{
	int i,j,k,n,m;
	int T=0;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		T++;
		if(T!=1)printf("\n");
		printf("Case %d:\n",T);
		for(i=1;i<=n;i++)h[i]=i,f[i]=1;
		for(i=1;i<=m;i++)
		{
			char s[10];
			scanf("%s",s);
			if(strcmp(s,"M")==0)
			{
				int a,b;
				scanf("%d%d",&a,&b);
				int ha=findhead(a);
				int hb=findhead(b);
				if(ha!=hb)
				{
					h[hb]=ha;
					f[ha]+=f[hb];
				}
			}
			else
			{
				int a,ha;
				scanf("%d",&a);
				ha=findhead(a);
				printf("%d\n",f[ha]);

			}
		}
	}
	return 0;
}