P1197 【[JSOI2008]星球大战】解题报告：并查集

这个题是一个倒过来的并查集，比较像[**P1653 猴子**](https://www.luogu.org/problemnew/show/P1653) 本题的目的是各个时间求联通块的个数，从最后时刻往前做，并查集的初始状态即被破坏后的图。 主要思想是，并查集中处于一个联通块的祖先结点相等，当任意祖先不同两个联通块联通时，联通块会减少一个（同时当破坏的被恢复时会增加一个），通过这种操作可以知道目前有多少个联通块。 而本题只需要知道是否在一个并查集中就可知道是否增删联通块了，因此核心算法不是很难。 具体操作说明附在代码里 本题注意事项 **1. 当调用祖先时，千万注意用find函数而不是s数组** **2. 本题的下标是从$0$开始到$n-1$的，注意越界** ```cpp #include<cstdio> #include<cstring> int s[400001];//并查集祖先数组 struct node { int n; node *next;//链表存图（或使用前向星） node(int n) { this->n=n; next=NULL; } node() { next=NULL; } }; node head[400001],*tail[400001];//用于存图 int b[400001];//b[i]存的是当时间为i时破坏的哪个点 bool g[400001];//g[i]表示现在i是否在图中 bool cnt[400001];//数联通块时是否被数过 int ans[400001];//ans[i]存储时刻为i时联通块个数，ans[0]存初始值 int my_find(int x) { if(s[x]==x) return x; return s[x]=my_find(s[x]);//递归路径压缩 } void my_union(int x,int y) { s[my_find(y)]=my_find(x); } int main() { memset(cnt,0,sizeof(cnt)); memset(g,true,sizeof(g)); int n,m,x,y; scanf("%d%d",&n,&m); for(int i=0;i<n;i++)//初始化并查集和链表 { s[i]=i; tail[i]=&head[i]; } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); tail[x]->next=new node(y); tail[y]->next=new node(x); tail[x]=tail[x]->next; tail[y]=tail[y]->next; } int k; scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%d",&b[i]); g[b[i]]=0;//i时刻b[i]不在图中 } for(int i=0;i<n;i++)//最终状态下剩余多少个联通块，之后也会用到 { if(g[i]==false)//起点此时不在图中 continue; node *p=&head[i]; while(p->next!=NULL) { p=p->next; if(g[p->n]==false)//终点此时不在图中 continue; my_union(p->n,i); } } int sum=0; for(int i=0;i<n;i++) if(cnt[my_find(s[i])]==false) { sum++;//数联通块个数 cnt[my_find(s[i])]=true;//表示s[i]这个祖先的联通块已经被数过 } sum-=k;//表示多余的被删去的点，稍后再插入 ans[k]=sum;//这是全部做完后的 int tmp=-1,w; for(int i=k;i>=1;i--)//i做到1可以减少一开始重复进行的ans[0] { tmp=-1;//tmp意思是减少了多少个联通块，也可以直接在sum上加1，后面的tmp同理-1 w=b[i]; g[w]=true;//循环是倒序，这个时刻之前该点被释放 node *p=&head[w]; while(p->next!=NULL) { p=p->next; if(g[p->n]==false) continue; if(my_find(p->n)!=my_find(w)) { tmp++; my_union(p->n,w); } } sum-=tmp; ans[i-1]=sum;//即在i时刻删点之前，答案是i-1的 } for(int i=0;i<=k;i++) printf("%d\n",ans[i]);//输出答案 return 0; } ``` $Finish$