题目链接
$\color{blue}{POJ 1988.Cube Stacking}$
并查集
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30010;
int p[N],cnt[N],d[N];
void init(){
for(int i = 0;i<N;i++)p[i] = i,d[i] = 0,cnt[i] = 1;
}
int Find(int x){
int px = p[x];
if(x!=px)p[x] = Find(p[x]),d[x]+=d[px];
return p[x];
}
void Union(int x,int y){
int a,b;
a = Find(x);
b = Find(y);
p[a] = b;
d[a] = cnt[b];
cnt[b]+=cnt[a];
}
int main(){
int P;
scanf("%d",&P);
init();
while(P--){
int x,y;
char op;cin>>op;
if(op=='M'){
cin>>x>>y;
Union(x,y);
}
else{
cin>>x;
Find(x);
cout<<d[x]<<endl;
}
}
return 0;
}