題目大意:給定一個無向圖,求聯通塊個數,以及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--]); }