并查集的删除操作:建立映射id[n]=n,忽视删除的点n,当n需要再入集合时,id[n]=n+1。
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; #define N 2000000 int id[10005],p[N]; int n,num; void init() { for(int i=1;i<=n;i++) p[i]=i,id[i]=i; } int find(int k) { if(p[k]==k) return k; int t=find(p[k]); p[k]=t; return t; } void U(int k1,int k2) { p[k2]=k1; } int main() { while(scanf("%d",&n)!=EOF) { init(); num=n; char t; int yes=0,no=0,a,b; while(1) { cin>>t; if(t=='e') break; else if(t=='c') { scanf("%d%d",&a,&b); int k1=find(id[a]),k2=find(id[b]); if(k1!=k2) U(k1,k2); } else if(t=='q') { scanf("%d%d",&a,&b); int k1=find(id[a]),k2=find(id[b]); if(k1==k2) yes++; else no++; } else { scanf("%d",&a); id[a]=++num; p[id[a]]=id[a]; } } printf("%d , %d\n",yes,no); } return 0; }