POJ 1988 Cube Stacking (种类并查集) - c++编程基础

题目地址：POJ 1988

这道题的查找合并的方法都能想的到，就是一点没想到，我一直天真的以为查询的时候，输入后能马上输出，这样的话在合并的时候就要所有的结点值都要算出来，但是经过路径压缩之后，没办法全部都处理到，如果不压缩妥妥的TLE。。于是看了看网上的题解。才发现自己是多么的天真（ben，四声）。。在查询的时候只要找一次跟就可以了。。这样不需查询的也就没必要处理出来。反而更省时。

这题的基本思路是很好想的。另开两个数组，一个记录以此节点为根的子节点的数目（这样合并的时候只需要加另一个根的数目就行了），另一个用来记录这个结点下面的点的数目，即需要输出的答案。然后分别在查找和合并的时候进行维护就可以了。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; int bin[31000], rank[31000], num[31000]; int find1(int x) { int y; if(bin[x]!=x) { y=bin[x]; bin[x]=find1(bin[x]); rank[x]+=rank[y]; } return bin[x]; } void join(int x, int y) { int f1=find1(x); int f2=find1(y); if(f1!=f2) { bin[f1]=f2; rank[f1]+=num[f2]; num[f2]+=num[f1]; } } int main() { int n, a, b, i, f1, f2; char c; scanf("%d",&n); for(i=1;i<=30000;i++) { bin[i]=i; rank[i]=0; num[i]=1; } while(n--) { getchar(); scanf("%c",&c); if(c=='M') { scanf("%d%d",&a,&b); join(a,b); } else { scanf("%d",&a); find1(a); printf("%d\n",rank[a]); } } return 0; }