题目
联通快嘛，就用并查集。
正着不好处理，反着来十分方便。这也是并查集的一种基本用法啊。
#include<bits/stdc++.h> #define N 200000 using namespace std; int f[2*N+1]; int find(int x) { return f[x]==x?x:f[x]=find(f[x]); } int m,n,x,y; int q,A[2*N+1]; int Ans,data[2*N+1]; bool survive[2*N+1]; vector <int> E[2*N+1]; #define add(x,y) \ E[x].push_back(y); int main() { scanf("%d %d",&n,&m); for(int i=0;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); } memset(survive,true,sizeof(survive)); scanf("%d",&q); Ans=n; for(int i=1;i<=q;i++) scanf("%d",&A[i]),survive[A[i]]=false,Ans--; for(int i=1;i<=n;i++) { if(survive[i]) { for(int j=0;j<E[i].size();j++) { int u=E[i][j]; if(!survive[u])continue; int fx=find(i),fy=find(u); if(fx!=fy)f[fy]=fx,Ans--; } } } for(int i=q;i>=1;i--) { data[i]=Ans; Ans++; survive[A[i]]=true; for(int j=0;j<E[A[i]].size();j++) { int u=E[A[i]][j]; if(!survive[u])continue; int fx=find(A[i]),fy=find(u); if(fx!=fy)f[fy]=fx,Ans--; } } printf("%d\n",Ans); for(int i=1;i<=q;i++) printf("%d\n",data[i]); return 0; }