http://www.lydsy.com/JudgeOnline/problem.php?id=1015 并查集模板题是不是？ 我们可以倒序处理，先计算出所有被攻击的星球消失以后的连通块数目，然后根据倒序分别加回被攻击的星球，这个统计和合并用并查集维护一下就好了 每合并完一次不要忘记把被攻击的星球自己算进去
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> using namespace std; int p[400001],nex[400001],head[400001],x[200001],y[200001],nedge=0; int ans[400010],r[400010],fa[400001]; bool b[400010]={0}; inline int getfather(int v){ if(fa[v]==v)return v; fa[v]=getfather(fa[v]); return fa[v]; } inline void addedge(int a,int b){ nedge++;p[nedge]=b; nex[nedge]=head[a]; head[a]=nedge; } int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x[i],&y[i]); addedge(x[i],y[i]); addedge(y[i],x[i]); } int k;scanf("%d",&k); for(int i=1;i<=k;i++){ scanf("%d",&r[i]); b[r[i]]=1; } for(int i=1;i<=n;i++)fa[i]=i; int sum=n-k; for(int i=1;i<=m;i++){ int fx=getfather(x[i]),fy=getfather(y[i]); if(!b[x[i]]&&!b[y[i]]&&fx!=fy){ fa[fx]=fy;sum--; } } ans[k+1]=sum; for(int i=k;i>0;i--){ b[r[i]]=0; int kk=head[r[i]]; while(kk){ int fx=getfather(r[i]),fy=getfather(p[kk]); if(!b[p[kk]]&&fx!=fy)fa[fx]=fy,sum--; kk=nex[kk]; } sum++;ans[i]=sum; } for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]); return 0; }