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; 
} 

 

作者：Java_beginer1