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

2018-04-14 17:31:11


这个题是一个倒过来的并查集,比较像P1653 猴子

本题的目的是各个时间求联通块的个数,从最后时刻往前做,并查集的初始状态即被破坏后的图。

主要思想是,并查集中处于一个联通块的祖先结点相等,当任意祖先不同两个联通块联通时,联通块会减少一个(同时当破坏的被恢复时会增加一个),通过这种操作可以知道目前有多少个联通块。

而本题只需要知道是否在一个并查集中就可知道是否增删联通块了,因此核心算法不是很难。

具体操作说明附在代码里

本题注意事项

1. 当调用祖先时,千万注意用find函数而不是s数组

2. 本题的下标是从$0$开始到$n-1$的,注意越界

#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$