[JSOI 2008] 星球大战

知识点

逆序处理、并查集、动态图连通性

解题思路

先标记所有被攻击节点，只把最终存活节点及边加入并查集，统计最终连通块。再逆序恢复每个节点：先增加一个独立连通块，再与已存活邻居合并，每次成功合并使数量减1。逆序记录后正序输出初始和每次攻击后的结果。

正确性说明

初始建出的并查集恰对应全部删除后的图。恢复节点时，新增的连接只有该点通向存活邻居的边，逐条合并恰好恢复前一个时刻的连通关系。由逆序归纳，各时刻连通块数量均正确。

易错点

编号从0开始；被毁节点不算孤立连通块；同一分量的多条边不能多减；输出k+1个状态。

复杂度

时间O((n+m)α(n))，空间O(n+m)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct DSU{vector<int>p,sz;DSU(int n):p(n),sz(n,1){iota(p.begin(),p.end(),0);}int find(int x){while(x!=p[x])x=p[x]=p[p[x]];return x;}bool join(int x,int y){x=find(x);y=find(y);if(x==y)return false;if(sz[x]<sz[y])swap(x,y);p[y]=x;sz[x]+=sz[y];return true;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<int>>g(n);vector<pair<int,int>>edges(m);for(auto&[u,v]:edges){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}int k;cin>>k;vector<int>del(k),ans(k+1);vector<char>on(n,1);for(int&x:del)cin>>x,on[x]=0;DSU d(n);int cnt=n-k;for(auto[u,v]:edges)if(on[u]&&on[v]&&d.join(u,v))--cnt;ans[k]=cnt;for(int i=k-1;i>=0;i--){int u=del[i];on[u]=1;++cnt;for(int v:g[u])if(on[v]&&d.join(u,v))--cnt;ans[i]=cnt;}for(int v:ans)cout<<v<<'\n';}