这是传送门
正难即反
我们先把所有安全的边先连起来，
然后倒序枚举每个攻击，对于一个攻击，并查集维护被攻击点与其他点的关系即可
#include<bits/stdc++.h> #define N 400005 #define M 200005 using namespace std; int n,m,tot,first[N],k,at[N]; bool broken[N]; struct node { int from,to,next; }edge[2*M]; inline void addedge(int x,int y) { tot++; edge[tot].from=x; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } int father[N]; inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } inline void merge(int x,int y) { int ax=getfather(x),bx=getfather(y); if(ax!=bx) father[ax]=bx; } int ans[N]; int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=0;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } cin>>k; for(int i=1;i<=k;i++) { cin>>at[i]; broken[at[i]]=true; } int cnt=n-k; //先连安全边 for(int i=1;i<=2*m;i++) { if(!broken[edge[i].from]&&!broken[edge[i].to]&&getfather(edge[i].from)!=getfather(edge[i].to)) { merge(edge[i].from,edge[i].to); cnt--; } } ans[k+1]=cnt; for(int i=k;i>=1;i--) { //修复一个点 cnt++; broken[at[i]]=false; for(int j=first[at[i]];j;j=edge[j].next) { if(!broken[edge[j].to]&&getfather(at[i])!=getfather(edge[j].to)) { cnt--; merge(at[i],edge[j].to); } } ans[i]=cnt; } for(int i=1;i<=k+1;i++) cout<<ans[i]<<'\n'; return 0; }
