又犯了zz的错误……
需要注意的是，被毁掉的星球是不算一个联通块的（可能只有我这么算吧= =）
离线下来时间倒流，就变成了向图里加星球，也就是用并查集维护联通，在用tot变量记录当前答案，每加一个星球就tot++，每合并一个联通块就tot--
注意始终没有被毁掉的星球应该在时间倒流前就加进图里
#include<iostream>#include<cstdio>#include<vector>using namespace std;const int N=1000005;int n,m,q,f[N],b[N],ans[N];bool v[N];vector<int>a[N];int read(){ ???int r=0,f=1; ???char p=getchar(); ???while(p>‘9‘||p<‘0‘) ???{ ???????if(p==‘-‘) ???????????f=-1; ???????p=getchar(); ???} ???while(p>=‘0‘&&p<=‘9‘) ???{ ???????r=r*10+p-48; ???????p=getchar(); ???} ???return r*f;}int zhao(int x){ ???return f[x]==x?x:f[x]=zhao(f[x]);}int main(){ ???n=read(),m=read(); ???for(int i=1;i<=m;i++) ???{ ???????int x=read()+1,y=read()+1; ???????a[x].push_back(y),a[y].push_back(x); ???} ???for(int i=1;i<=n;i++) ???????f[i]=i; ???int tot=0; ???q=read(); ???for(int i=q;i>=1;i--) ???????b[i]=read()+1,v[b[i]]=1; ???for(int i=1;i<=n;i++) ???????if(!v[i]) ???????{ ???????????tot++; ???????????for(int j=0;j<a[i].size();j++) ???????????????if(!v[a[i][j]]) ???????????????{ ???????????????????int fu=zhao(i),fv=zhao(a[i][j]); ???????????????????if(fu!=fv) ???????????????????{ ???????????????????????f[fu]=fv; ???????????????????????tot--; ???????????????????} ???????????????} ???????} ???for(int i=1;i<=q;i++) ???{ ???????ans[i]=tot++; ???????v[b[i]]=0; ???????for(int j=0;j<a[b[i]].size();j++) ???????????if(!v[a[b[i]][j]]) ???????????{ ???????????????int fu=zhao(b[i]),fv=zhao(a[b[i]][j]); ???????????????if(fu!=fv) ???????????????{ ???????????????????f[fu]=fv; ???????????????????tot--; ???????????????} ???????????} ???} ???printf("%d\n",tot); ???for(int i=q;i>=1;i--) ???????printf("%d\n",ans[i]); ???return 0;}bzoj 1015: [JSOI2008]星球大战starwar【并查集】
原文地址：https://www.cnblogs.com/lokiii/p/9404657.html