http://poj.org/problem?id=1988 &&hdu 2818并查集的良好应用

http://poj.org/problem?id=1988 &&hdu 2818并查集的很好应用

这题在去年的做并查集专题的时候，就看过当时不理解题意，一直放到现在才解决，真心蒟蒻，ORZ，，，弱爆了，最近状态不是很好，所以要调整心态；

本题是在并查集查找时，回溯更新under[]数组的值；用到三个数组，fa[x],记录x的父节点，经过路径压缩后fa[x]的值就是x所属的集合；con[x],表示x所在堆的个数，under[x],表示x下面节点数；很好的并查集题目；

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;
const int N=30003;
int fa[N],con[N],under[N];
int find(int x)
{
  int t;
   if(x!=fa[x])
   {
    t=find(fa[x]);
	under[x]+=under[fa[x]];
	fa[x]=t;
   }
   return fa[x];
}
void init()
{
 for(int i=0;i<N;i++)
 {
   fa[i]=i;con[i]=1;under[i]=0;
 }
}
void Union(int x,int y)
{
 int xx=find(x),yy=find(y);
   if(xx!=yy)
   {
     under[xx]=con[yy];
	 con[yy]+=con[xx];
	 fa[xx]=yy;
   }
}
int main()
{
   int p,a,b;
   char op[11];
    while(~scanf("%d",&p))
	{
	   init();
	   while(p--)
	   {
	    scanf("%s",op);
		if(op[0]=='M')
		{
		scanf("%d%d",&a,&b);
		Union(a,b);
		}else
		{
		scanf("%d",&a);
		  find(a);//此处必须有，不然会wa的，要及时更新
		printf("%d\n",under[a]);
		}
	   }
	}
 return 0;
}