Cube Stacking

思路

先贴个翻译

很明显是裸裸的并查集。

先开一个fa数组表示这个箱子在哪个集合中，要合并就直接把fa【x】 = y就表示集合x加入到集合y里面

开一个ran数组统计每个集合中的数量，合并的时候就把该集合的ran加到另外一个集合就好

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[30005],ran[30005],size[30005];
inline void init(){
    for(int i=1;i<=30005;i++){
        fa[i]=i;
        ran[i]=0;
        size[i]=1;
    }
}
int find(int x){
    if(x==fa[x])    return x;
    else{
        int t=fa[x];
        fa[x]=find(fa[x]);
        ran[x]+=ran[t];
        return fa[x];
    }
}
inline void merge(int i,int j){
    int x=find(i),y=find(j);
    fa[x]=y;
    ran[x]+=size[y];
    size[y]+=size[x];
}
int main(){
    int t,a,b;
    char ch;
    init();
    scanf("%d",&t);
    while(t--){
        scanf(" %c",&ch);
        if(ch=='M'){
            scanf("%d%d",&a,&b);
            merge(a,b);
        }
        else{
            scanf("%d",&a);
            find(a);
            printf("%d\n",ran[a]);
        }
    }
}