题目大意：给定一个无向图，求联通块个数，以及k次每次摧毁一个点后的；联通块个数

将边和摧毁的点全记录下来，反着做即可。

注意被摧毁的点不能算作联通块

#include
  
   
#include
   
     #include
    
      #include
     
       #define M 400400 using namespace std; struct abcd{ int to,next; }table[M]; int head[M],tot; int n,m,q; int fa[M],stack[M],destroy[M],top,now; bool destroyed[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } inline void Unite(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx==fy) return ; --now; fa[fy]=fx; } inline void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } int main() { int i,j,x,y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); ++x;++y; Add(x,y); Add(y,x); } cin>>q; for(i=1;i<=q;i++) { scanf("%d",&destroy[i]); ++destroy[i]; destroyed[destroy[i]]=1; } now=n-q; for(j=1;j<=n;j++) if(!destroyed[j]) for(i=head[j];i;i=table[i].next) if(!destroyed[table[i].to]) Unite(j,table[i].to); stack[++top]=now; for(j=q;j;j--) { x=destroy[j]; destroyed[x]=0; ++now; for(i=head[x];i;i=table[i].next) if(!destroyed[table[i].to]) Unite(x,table[i].to); stack[++top]=now; } while(top) printf("%d\n",stack[top--]); }