先上一波题目 https://www.luogu.org/problem/P1197
很明显删除的操作并不好处理 那么我们可以考虑把删边变成加边
只需要一波时间倒流就可以解决拉
储存删边顺序倒过来加边 问题便完美解决了qwq
#include<cstdio> #include<cstring> #include<algorithm> const int M=400007; using namespace std; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m,k,cnt=0,tot=0; int first[M],bomb[M],in[M],fa[M],ans[M]; struct node{int to,next;}e[M]; void ins(int x,int y){cnt++; e[cnt].to=y,e[cnt].next=first[x]; first[x]=cnt;} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void insert(int x){ //puts("qwq"); for(int i=first[x];i;i=e[i].next){ //printf("%d %d\n",x,e[i].to); int now=e[i].to; if(in[now]) continue; int p=find(x),q=find(now); if(p!=q){tot--; fa[p]=q;} } } int main(){ int x,y; n=read(); m=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) x=read()+1,y=read()+1,ins(x,y),ins(y,x); //printf("qwq%d\n",cnt); k=read(); for(int i=1;i<=k;i++) bomb[i]=read()+1,in[bomb[i]]=1; for(int i=1;i<=n;i++)if(!in[i]) tot++,insert(i); ans[k+1]=tot; //printf("%d\n",ans[k]); for(int i=k;i>=1;i--){ in[bomb[i]]=0; tot++; insert(bomb[i]); ans[i]=tot; } for(int i=1;i<=k+1;i++) printf("%d\n",ans[i]); return 0; }