poj 1988(并查集)

题意：进行m次操作，M x y 将包含x的集合移动到y上面，C x, 计算x下面有几个元素。

解题思路：这道题很容易想到用并查集，但是这里有点绕；最开始我想到的是建立一个num[x]，表示x以下的节点数，但这样会有一个问题，要更新num[x]时，必须要枚举哪些节点的父节点为p，由于节点数太多，所以TLE是难免的。。。。

这里有一个好办法：在算x以下节点数时，可以用x所在集合元素的个数 - 在它之上的个数 - 它本身。这样就可以避免枚举了。

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 30005;
int fa[maxn],cnt[maxn],top[maxn];

int find(int x)
{
	if(fa[x] == x) return x;
	int t = fa[x];
	fa[x] = find(fa[x]);
	top[x] += top[t];
	return fa[x];
}

void Union(int x,int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx != fy)
	{
		fa[fy] = fx;
		top[fy] = cnt[fx];
		cnt[fx] += cnt[fy];
	}
}

int main()
{
	int p,a,b;
	char ch;
	for(int i = 1; i < maxn; i++)
	{
		fa[i] = i;
		top[i] = 0;
		cnt[i] = 1;
	}
	scanf("%d",&p);
	while(p--)
	{
		getchar();
		ch = getchar();
		if(ch == 'M')
		{
			scanf("%d%d",&a,&b);
			Union(a,b);
		}
		else 
		{
			scanf("%d",&a);
			int f = find(a);
			printf("%d\n",cnt[f] - top[a] - 1);
		}
	}
	return 0;
}