[Luogu 1197] JSOI2008 星球大战
<题目链接>
我算是真的沦为联赛选手了。
并查集裸题。
比较麻烦的是删点。
但是从后往前加点就好操作很多。
所以考虑离线，先存图，然后没被删的点之间，有边就合并。
每加一个点进来，把连着这个点且当前没被删的点并进来，更新连通块个数并存入答案。
最终按顺序输出答案即可。
#include <cstdio>#include <cstring>const int MAXN=400010,MAXM=200010;bool gone[MAXN];int n,m,k,sum,q[MAXN],ans[MAXN];struct Edge{ ???int to; ???Edge *next; ???Edge(int to,Edge* next):to(to),next(next){} ???~Edge(void) ???{ ???????if(next!=nullptr) ???????????delete next; ???}}*head[MAXN];class UFS{ ???private: ???????bool exist[MAXN]; ???????int f[MAXN]; ???????int Find(int x) ???????{ ???????????return x==f[x] ? x : f[x]=Find(f[x]); ???????} ???public: ???????UFS(int n) ???????{ ???????????memset(exist,0,sizeof exist); ???????????for(int i=0;i<n;++i) ???????????{ ???????????????head[i]=nullptr; ???????????????f[i]=i; ???????????} ???????} ???????~UFS(void) ???????{ ???????????for(int i=0;i<n;++i) ???????????????delete head[i]; ???????} ???????void Merge(int x,int y) ???????{ ???????????f[Find(y)]=Find(x); ???????} ???????int Count(void) ???????{ ???????????int ans=0; ???????????for(int i=0,t;i<n;++i) ???????????????if(!gone[i] && !exist[t=Find(i)]) ???????????????{ ???????????????????++ans; ???????????????????exist[t]=1; ???????????????} ???????????return ans; ???????} ???????bool Connected(int x,int y) ???????{ ???????????return Find(x)==Find(y); ???????}};void AddEdges(int u,int v){ ???head[u]=new Edge(v,head[u]); ???head[v]=new Edge(u,head[v]);}int main(int argc,char** argv){ ???scanf("%d %d",&n,&m); ???static UFS *S=new UFS(n); ???for(int i=1,x,y;i<=m;++i) ???{ ???????scanf("%d %d",&x,&y); ???????AddEdges(x,y); ???} ???scanf("%d",&k); ???for(int i=1;i<=k;++i) ???{ ???????scanf("%d",&q[i]); ???????gone[q[i]]=true; ???} ???for(int u=0;u<n;++u) ???????if(!gone[u]) ???????????for(Edge *i=head[u];i!=nullptr;i=i->next) ???????????{ ???????????????int v=i->to; ???????????????if(!gone[v]) ???????????????????S->Merge(u,v); ???????????} ???ans[k]=sum=S->Count(); ???for(int j=k,u;j>=1;--j) ???{ ???????++sum; ???????gone[u=q[j]]=false; ???????for(Edge *i=head[u];i!=nullptr;i=i->next) ???????{ ???????????int v=i->to; ???????????if(gone[v]==false && !S->Connected(u,v)) ???????????{ ???????????????--sum; ???????????????S->Merge(u,v); ???????????} ???????} ???????ans[j-1]=sum; ???} ???for(int i=0;i<=k;++i) ???????printf("%d\n",ans[i]); ???delete S; ???return 0;}谢谢阅读。
[Luogu 1197] JSOI2008 星球大战
原文地址：https://www.cnblogs.com/Capella/p/9130807.html