传送门
这道题看题目描述……联通具有传递性？很容易想到是并查集。
不过按照题目的描述似乎很麻烦……这样每次摧毁会令人很难受。不过这并不是问题，我们把它倒过来，从最终被摧毁的状态开始，直接往回加边，每次用并查集维护即可。
还有就是如何计算联通块数？一开始我智障般的想了好久……后来被mrclr一语道破：从一开始剩余的星球数开始计算，每次合并两个就将总数--，每次新加入一个星球先++，之后仿照上面的方式继续计算，把答案存起来即可。
上代码。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar(‘\n‘)using namespace std;const int M = 200005;typedef long long ll;int read(){ ???int ans = 0,op = 1; ???char ch = getchar(); ???while(ch < ‘0‘ || ch > ‘9‘) ???{ ???????if(ch == ‘-‘) op = -1; ???????ch = getchar(); ???} ???while(ch >= ‘0‘ && ch <= ‘9‘) ???{ ???????ans *= 10; ???????ans += ch - ‘0‘; ???????ch = getchar(); ???} ???return ans * op;}struct node{ ???int next,to,from;}e[M<<1];int n,m,x,y,des[M<<1],fa[M<<1],head[M<<1],ecnt,k,sum,ans[M<<1],p;bool vis[M<<1];void add(int x,int y){ ???e[++ecnt].to = y; ???e[ecnt].from = x; ???e[ecnt].next = head[x]; ???head[x] = ecnt;}int getfa(int x){ ???if(fa[x] == x) return fa[x]; ???else return fa[x] = getfa(fa[x]);}int main(){ ???n = read(),m = read(); ???rep(i,0,n-1) fa[i] = i; ???rep(i,1,m) x = read(),y = read(),add(x,y),add(y,x); ???k = read(),sum = n-k,p = n; ???rep(i,1,k) des[i] = read(),vis[des[i]] = 1; ???rep(i,0,n-1) ???{ ???????if(vis[i]) continue; ???????int r1 = getfa(i); ???????for(int j = head[i];j;j = e[j].next) ???????{ ???????????if(vis[e[j].to]) continue; ???????????int r2 = getfa(e[j].to); ???????????if(r1 != r2) fa[r2] = r1,sum--; ???????} ???} ???ans[k] = sum; ???per(i,k,1) ???{ ???????vis[des[i]] = 0,sum++; ???????int r1 = getfa(des[i]); ???????for(int j = head[des[i]];j;j = e[j].next) ???????{ ???????????if(vis[e[j].to]) continue; ???????????int r2 = getfa(e[j].to); ???????????if(r1 != r2) fa[r2] = r1,sum--; ???????} ???????ans[i-1] = sum; ???} ???rep(i,0,k) printf("%d\n",ans[i]); ???return 0;}JSOI2008 星球大战
原文地址：https://www.cnblogs.com/captain1/p/9557394.html