解题思路： 由判断联通问题想到并查集维护，但是如果每次询问都删去点跑dfs的话，显然是超时的。于是想到反着做，将删点问题转化为连边。 首先先处理出全部询问的星球被毁的联通块数，然后倒着加入询问，将与询问点联通的点遍历，记录联通块数。 输出技巧，因为是倒着处理的，可以将结果压入栈中。用栈储存结果。 详见代码
#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; const int maxn=400005; int r1,r2,head[maxn],s,n,m,x,y,f[maxn],des[maxn],v[maxn],cnt,k; stack<int >ans; struct node{ int from,to; }list[maxn*2]; void add(int x,int y){ list[++s].from=head[x]; list[s].to=y; head[x]=s; } int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void check(int x){ for (int i=head[x];i;i=list[i].from) { int u=list[i].to; if (v[u]) continue; r1=find(x);r2=find(u); if (r1!=r2){ cnt--;//合并一次 联通块少1 f[r1]=r2; } } if (v[x]) cnt++,v[x]=0;//如果当前点已经走过了，说明删多了， } int main(){ cin>>n>>m; for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x+1,y+1);add(y+1,x+1); } for (int i=1;i<=n;i++) f[i]=i; cin>>k; for (int i=1;i<=k;i++){ scanf("%d",&x);x++; des[i]=x; v[x]=1; } cnt=n-k;//类似于并查集的初始化，每个点独立成块 for (int i=1;i<=n;i++) if (!v[i]) check(i); ans.push(cnt); for (int i=k;i>=1;i--){ check(des[i]);ans.push(cnt); } while(!ans.empty()){ cout<<ans.top()<<endl; ans.pop(); } return 0; }