http://poj.org/problem?id=1988 &&hdu 2818並查集

這題在去年的做並查集專題的時候，就看過當時不理解題意，一直放到現在才解決，真心蒟蒻，ORZ，，，弱爆了，最近狀態不是很好，所以要調整心態；
本題是在並查集查找時，回溯更新under[]數組的值；用到三個數組，fa[x],記錄x的父節點，經過路徑壓縮後fa[x]的值就是x所屬的集合；con[x],表示x所在堆的個數，under[x],表示x下面節點數；很好的並查集題目；
[cpp]
#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 
        {   www.2cto.com
        scanf("%d",&a); 
          find(a);//此處必須有，不然會wa的，要及時更新 
        printf("%d\n",under[a]); 
        } 
       } 
    } 
 return 0; 
}