题目链接:https://www.nowcoder.com/acm/contest/106/C
题意是有一堆树,当你输入1的时候,将a,b森林合并起来,输入2的时候,将a这棵树从当前森林中分离出来,输入3的时候,查询a所在的森林里有多少棵树,输入为4的时候,判断a和b是否属于同一片森林。因为涉及到了并查集的删除操作,所以需要另外开辟辅助数组,然后需要注意的是,当查询一片森林中的树的个数的时候,如果重新遍历的话会超时,所以还需要一个siz数组来记录每一个根节点的森林的树的数量,在每次合并的时候,将合并的根节点的数目加上被合并的森林的树的数量就好了,需要注意的是在删除树的时候,要记得先将这片森林的数目减少一个。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 200005;
int n,m,T,ans,num;
int pre[MAXN],box[MAXN],siz[MAXN];
void init(){
for(int i=0;i<=MAXN;i++){
pre[i] = i;
box[i] = i;
siz[i] = 1;
}
}
int Find(int x){
if(box[x] != x){
box[x] = Find(box[x]);
}
return box[x];
}
void merge(int x,int y){
int fx = Find(x);
int fy = Find(y);
if(fx != fy){
box[fy] = fx;
siz[fx] += siz[fy];
// siz[fy] = 0;
}
}
int main()
{
int Case = 1;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
num = n + 1;
printf("Case #%d:\n",Case++);
while(m--){
scanf("%d",&ans);
if(ans == 1){
int a,b;
scanf("%d%d",&a,&b);
merge(pre[a],pre[b]);
}
else if(ans == 2){
int a;
scanf("%d",&a);
siz[Find(pre[a])]--; // 该森林中少一个树
pre[a] = num;
num++;
}
else if(ans == 3){
int a;
scanf("%d",&a);
printf("%d\n",siz[Find(pre[a])]);
}
else{
int a,b;
scanf("%d%d",&a,&b);
if(Find(pre[a]) != Find(pre[b]))printf("NO\n");
else printf("YES\n");
}
}
}
return 0;
}