@zzzc18
2017-08-04T14:54:57.000000Z
字数 705
阅读 1316
并查集
我们记录一下每个元素的编号pid[]
删除时,将删除的点编号变为一个先前未出现的值,fa等于他自己
#include<cstdio>
#include<cstring>
#define MAXN 2000000+9
using namespace std;
int fa[MAXN],pid[MAXN];
int n,ans1,ans2;
int Find(int x){
return fa[x]==x ? x : fa[x]=Find(fa[x]);
}
void merge(int x,int y){
int xx=Find(x);
int yy=Find(y);
fa[xx]=yy;
}
int main(){
while(scanf("%d",&n)!=EOF){
ans1=ans2=0;
int i;
for(i=0;i<=n;i++){
fa[i]=i;
pid[i]=i;
}
while(true){
char opt[2];
int x,y;
scanf("%s",opt);
if(opt[0]=='e')
break;
if(opt[0]=='c'){
scanf("%d%d",&x,&y);
x=pid[x];
y=pid[y];
merge(x,y);
}
if(opt[0]=='d'){
scanf("%d",&x);
pid[x]=++n;
fa[n]=n;
}
if(opt[0]=='q'){
scanf("%d%d",&x,&y);
x=pid[x];
y=pid[y];
int xx=Find(x);
int yy=Find(y);
if(xx==yy)
ans1++;
else
ans2++;
}
}
printf("%d , %d\n",ans1,ans2);
}
return 0;
}