并查集维护集合
这道题code写起来很容易
但有很多启示
这道题需要逆序做
为什么呢？
对于路径压缩的并查集来说，如果合并了。那么想要在分开是很难的。
而且这道题要求每步输出。但是！！ 这道题是先给操作，再统一输出！！ 我们就可以离线做
那么我们就可以逆序做
先处理最后的状态，然后倒着合并。这样的话，就可以很快的跑出来了
对于合并容易，分开难得数据结构。在要求支持分开的离线操作题中。我们可以将分开换做合并。 倒着做
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int f[401000];int find(int x){ ???if(f[x]==x) ???????return x; ???return f[x]=find(f[x]);}struct node{ ???int point; ???int nxt;};node l[401000];int head[401000],tail;int in[401000][2];void add(int x,int y){ ???l[++tail].point=y; ???l[tail].nxt=head[x]; ???head[x]=tail;}int able[400010];bool use[400010];int ans[400010];int main(){ ???int n,m,k; ???scanf("%d%d",&n,&m); ???for(int i=0;i<n;i++) ???????f[i]=i; ???int a,b; ???for(int i=1;i<=m;i++) ???{ ???????scanf("%d%d",&a,&b); ???????add(a,b);add(b,a); ???????in[i][0]=a; ???????in[i][1]=b; ???} ???scanf("%d",&k); ???for(int i=1;i<=k;i++) ???{ ???????scanf("%d",&able[i]); ???????use[able[i]]=true; ???} ???for(int i=1;i<=m;i++) ???{ ???????if(use[in[i][0]]||use[in[i][1]]) ???????????continue; ???????int f1=find(in[i][0]),f2=find(in[i][1]); ???????f[f1]=f2; ???} ???int tot=0; ???for(int i=0;i<n;i++) ???????if(find(i)==i&&!use[i]) ???????????tot+=1; ???for(int i=k;i>=1;i--) ???{ ???????ans[i]=tot; ???????for(int need=head[able[i]];need;need=l[need].nxt) ???????{ ???????????int f1=find(able[i]),f2=find(l[need].point); ???????????if(f1!=f2&&!use[l[need].point]) ???????????{ ???????????????tot-=1; ???????????????f[f1]=f2; ???????????} ???????} ???????tot+=1;//因为第一次合并时，集合数并不会减少，所以这里将tot补回来 ???????use[able[i]]=false; ???} ???ans[0]=tot; ???for(int i=0;i<=k;i++) ???????printf("%d\n",ans[i]);}/*5 70 10 20 42 32 11 33 13241*/