这是今天写的比较有价值的一道题，晚上写了大概一个多小时，主要还是在debug，出得很妙，好题👍
P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态
思路：如果我们按照顺序一个一个的去计算毁灭一个星球之后还剩多少个连通块，那么我们还得每次去更新邻接点的祖宗节点，显然是超时的。既然删边很难，那么我们考虑加边操作，即先计算出k个星球全部毁灭还有多少个连通块（先对k个星球做个标记，然后剩下的n-k个星球进行通过邻接表进行连边操作），然后依次加入第k个，k-1....星球的邻边，加入第i个毁灭星球的邻边时，我们用set<int> s存储其邻边包含多少个连通块也就是邻接点有多少个不同的祖宗节点，每次将i星球的祖宗节点更新为不同值得邻接点祖宗节点，同时邻接点不能是毁灭星球，当第i个毁灭星球的邻接点遍历完成时，我们取消对它的标记，以便第1~i-1个毁灭星球对它进行连边，然后我们的s存储了多少个数表明第i个毁灭星球能合并多少个连通块，所以第i个星球毁灭之前连通块的个数有：第i+1个星球毁灭之前的连通块数-s的大小+1（加1是因为最终合并成一个连通块了，所以总的连通块个数减少了s.size()-1)
Code:
constexpr int N=4e5+5,mod=1e9+7;map<int,int> mp;
int destruct[N],f[N],n,m,ans[N];
int h[N],e[N],ne[N],idx;
PII q[N];void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int find(int i)
{if(f[i]!=i) f[i]=find(f[i]);return f[i];
}void solve()
{cin>>n>>m;memset(h,-1,sizeof h);int k=0;for(int i=0;i<n;i++) f[i]=i;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);q[i]={a,b};}int p;cin>>p;for(int i=0;i<p;i++){cin>>destruct[i];mp[destruct[i]]=1;}#define fi first#define se secondfor(int i=1;i<=m;i++){int a=q[i].fi,b=q[i].se;if(mp[a]||mp[b]) continue;int pa=find(a),pb=find(b);if(pa!=pb){f[pa]=pb;}}int cnt=0;for(int i=0;i<n;i++)if(f[i]==i&&!mp[i]) cnt++;ans[p]=cnt;for(int i=p-1;i>=0;i--){int x=destruct[i];set<int> s;int px=find(x);// if(i==3) cout<<x<<' '<<px<<endl;// s.insert(px);for(int j=h[x];~j;j=ne[j]){int j1=e[j];if(mp[j1]==1) continue;int pj=find(j1); s.insert(pj);// if(i==3) // cout<<j1<<"----"<<pj<<endl;if(pj!=px){f[px]=pj;// if(i==3)//cout<<"连接："<<px<<' '<<pj<<endl;px=pj;//这个地方别忘记更新毁灭星球的祖宗节点}}mp[x]=0;// if(i==2) cout<<"---"<<s.size()<<endl;ans[i]=ans[i+1]-(s.size())+1;}for(int i=0;i<=p;i++) cout<<ans[i]<<endl;
}int32_t main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;//cin>>t;t=1;while(t--) solve();
}
