传送门
看到联通块，好像跟并查集、强连通分量有关系吧，仔细一看跟哪些点属于哪些块没关系，只关心联通块数量，那么应该可以用并查集做。继续看，这是一道删边的题，好像很难维护删边，我们又知道并查集是可以维护加边的，那么我们就倒过来做好了。
#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 400005struct Node{ ???int u,v;}E[MAXN];struct edge{ ???int v,next;}G[MAXN];int fa[MAXN],vis[MAXN];int ed[MAXN],ans[MAXN];int head[MAXN];int N,M,K,tot=0;int find(int x){ ???return x==fa[x]?x:fa[x]=find(fa[x]);}inline void merge(int u,int v){ ???fa[find(u)] = find(v);}inline void add(int u,int v){ ???G[++tot].v = v ;G[tot].next = head[u];head[u] = tot;}int main(){ ???scanf("%d%d",&N,&M); ???for(register int i=0;i<N;++i){ ???????fa[i] = i; ???} ???std::memset(head,0,sizeof(head)); ???std::memset(vis,0,sizeof(vis)); ???for(register int i=1;i<=M;++i){ ???????scanf("%d%d",&E[i].u,&E[i].v); ???????add(E[i].u,E[i].v); ???????add(E[i].v,E[i].u); ???} ???scanf("%d",&K); ???int count = N-K; ???for(register int i=K;i>=1;--i){ ???????scanf("%d",&ed[i]); ???????vis[ed[i]] = 1; ???} ???for(register int i=1;i<=M;++i){ ???????int u = E[i].u;int v = E[i].v; ???????if(vis[u]||vis[v]||(find(u)==find(v)))continue; ???????merge(u,v); ???????count--; ???} ???ans[0] = count; ???for(register int i=1;i<=K;++i){ ???????vis[ed[i]] = 0; ???????count++; ???????for(register int j=head[ed[i]];j;j=G[j].next){ ???????????int v = G[j].v; ???????????if(!vis[v]&&find(v)!=find(ed[i])){ ???????????????merge(v,ed[i]); ???????????????count--; ???????????} ???????} ???????ans[i] = count; ???} ???for(register int i=K;i>=0;--i){ ???????printf("%d\n",ans[i]); ???} ???return 0;}[luogu1197] [JSOI2008]星球大战
原文地址：https://www.cnblogs.com/Neworld2002/p/9814046.html