#include<stdio.h>
#define N 30001

int count[N], num[N], pre[N];

int find(int x)
{
	if(pre[x] == x)
	{
		return x;
	}
	int t = find(pre[x]);
	count[x] += count[pre[x]];
	pre[x] = t;
	return t;
}

void Union(int x, int y)
{
	int i = find(x);
	int j = find(y);
	if(i == j)
	{
		return;
	}
	count[i] = num[j];
    num[j] += num[i];
	pre[i] = j;
}



int main()
{
	int i, x, y, n;
	char s[2];
	scanf("%d",&n);
	for(i = 1; i <= N; i++)
	{
		pre[i] = i;
		num[i] = 1;
		count[i] = 0;
	}
	for(i = 0; i < n; i++)
	{
		scanf("%s",s);
		if(s[0] == 'M')
		{
			scanf("%d%d",&x,&y);	
			Union(x,y);
		}
		else if(s[0] == 'C')
		{
			scanf("%d",&x);
			int c = find(x);
			printf("%d\n",count[x]);
		}
	}
	return 0;
}

• Re:终于AC了，原来只是一个小小的错误，还我WA了好多次……无语，po一下偶的代码 (19) usc_xuchen 2012-09-28 13:58:46
  • 确实很简洁 (23) ysymi 2013-03-23 10:12:10