P1197 【[JSOI2008]星球大战】解题报告:并查集
wjyyy
2018-04-14 17:31:11
这个题是一个倒过来的并查集,比较像[**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$