原题链接：https://www.luogu.org/problemnew/show/P1197
题意简述：给出n个点的无向图，每次删去一个点，询问当前的连通块个数。
删点太难做，不如加点，首先将询问读取，然后离线倒着处理。
标记每个已经删去的点，首先计算出所有没标记的点一共组成多少个连通块。
然后依次加点，同时删去标记，首先将连通块个数增加1，而当前点每与其他的连通块相连，连通块个数减少1，最终算出答案即可
能够保证每条边最多走两遍，并查集时间复杂度不计的话，时间复杂度O（n）
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;void read(int &y){ ???y=0;char x=getchar(); ???while(x<‘0‘||x>‘9‘) x=getchar(); ???while(x>=‘0‘&&x<=‘9‘) ???{ ???????y=y*10+x-‘0‘; ???????x=getchar(); ???}}int n,m,cnt,ans;int f[400005],head[400005];int q[200005],vis[400005];struct edge{ ???int u,v;}e[400005];void add(int u,int v){ ???e[++cnt].u=head[u]; ???e[cnt].v=v; ???head[u]=cnt;}int find(int x){ ???if(x==f[x]) return x; ???return f[x]=find(f[x]);}int main(){ ???int u,v; ???read(n);read(m); ???for(int i=1;i<n;i++) f[i]=i; ???memset(head,-1,sizeof(head)); ???for(int i=0;i<m;i++) ???{ ???????read(u);read(v); ???????add(u,v);add(v,u); ???} ???read(m); ???for(int i=0;i<m;i++) ???{ ???????read(q[i]); ???????vis[q[i]]=1; ???} ???ans=n-m; ???for(int i=0;i<n;i++) ???{ ???????if(vis[i]==1) continue; ???????for(int j=head[i];j!=-1;j=e[j].u) ???????{ ???????????if(vis[e[j].v]==1) continue; ???????????u=find(i); ???????????v=find(e[j].v); ???????????if(u==v) continue; ???????????f[v]=u; ???????????ans--; ???????} ???} ???q[m]=ans; ???for(int i=m-1;i>=0;i--) ???{ ???????vis[q[i]]=0; ???????int tans=-1; ???????for(int j=head[q[i]];j!=-1;j=e[j].u) ???????{ ???????????if(vis[e[j].v]==1) continue; ???????????u=find(q[i]); ???????????v=find(e[j].v); ???????????if(u==v) continue; ???????????f[u]=v; ???????????tans++; ???????} ???????q[i]=q[i+1]-tans; ???} ???for(int i=0;i<=m;i++) printf("%d\n",q[i]); ???return 0;}[JSOI2008]星球大战
原文地址：https://www.cnblogs.com/zeroform/p/8454841.html