hdu2818 Building Block 并查集

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2818

//其实rank[x]也能表示x下面的元素个数，但为什么不用rank[x]呢，因为需要维护每个rank[x]，而我们只希望有一个rank，即根节点的总子节点个数 

//union操作最多3w，而find操作可以有100w，所以union操作可以O(n)，但find操作必须O(1) 

//所以原来准备 rank[find(x)]-up[x]就是在x下面的点数，但是find操作仍然不小，我们希望直接保存x下面的点数作为dis[x] 

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

const int maxn=30000;
int t,x,y,tmp,ans;
char cmd;

struct disjoint_set{
    
    int parent[maxn],dis[maxn],rank[maxn];//rank[root]表示根节点下的节点总数（包括根节点） 
    void makeset(){
        for(int i=0;i<maxn;i++)
        {
            dis[i]=0;
            rank[i]=1;
            parent[i]=i;
        }
    }
    int find(int x){
        
        if(x!=parent[x]){
            
            int root=find(parent[x]);
            dis[x]+=dis[parent[x]];
            parent[x]=root;
            return parent[x];
        }
        return x;
    }

    
    void union_set(int x,int y){//就是把x加到y上面 
        x=find(x);
        y=find(y);
        if(x==y)//在同一个集上 
            return;
        
        parent[x]=y;
        dis[x]+=rank[y];
        rank[y]+=rank[x];
    }
}s;

int main(){
    cin>>t;
    s.makeset();
    while(t--)
    {
        cin>>cmd;
        if(cmd=='M'){
            cin>>x>>y;
            s.union_set(x,y);
        }
        else{
            cin>>x;
            s.find(x);//因为union里面没有执行，所以回答的时候还要再执行一次find 
            cout<<s.dis[x]<<endl;
        }
    }
    return 0;
}