[BZOJ4998]星球联盟(LCT,并查集)

发布于 2018-01-21  137 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4998]星球联盟(LCT,并查集)

Description

在遥远的S星系中一共有N个星球,编号为1…N。其中的一些星球决定组成联盟,以方便相互间的交流。但是,组成联盟的首要条件就是交通条件。初始时,在这N个星球间有M条太空隧道。每条太空隧道连接两个星球,使得它们能够相互到达。若两个星球属于同一个联盟,则必须存在一条环形线路经过这两个星球,即两个星球间存在两条没有公共隧道的路径。为了壮大联盟的队伍,这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条新轨道建成后,可能会使一些星球属于同一个联盟。你的任务是计算出,在一条新隧道建设完毕后,判断这条新轨道连接的两个星球是否属于同一个联盟,如果属于同一个联盟就计算出这个联盟中有多少个星球。

Http

BZOJ

Tag

LCT,并查集

题目大意

简单一句话,动态维护边双联通分量

解决思路

在线做法
用并查集1维护连通性,并用LCT维护在同一个联通块(注意这里还不是双联通)的点。
如果遇到加入一条边时,两个端点已经在同一个联通块了,说明新形成了一个双联通分量,找出这两点之间的路径,把这个环缩成一个点(这个用并查集2维护),环上所有点都指向一个编号,\(dfs\)一遍可以遍历所有这些点,把它们的\(size\)累加。
要注意,因为我们有缩点的操作,所以在\(LCT\)的各种操作中都要注意及时\(find\)找到编号。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=200110;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int rev;
};

int n,m,P;
Splay_Data S[maxN];
int Stack[maxN];
int Set1[maxN],Set2[maxN];
int Size[maxN];

bool Isroot(int x);
void PushDown(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
void Makeroot(int x);
void Link(int x,int y);
int Add_Edge(int u,int v);
int Find(int *f,int x);
void dfs(int now,int fa);

int main()
{
    scanf("%d%d%d",&n,&m,&P);
    for (int i=1;i<=n;i++) Size[i]=1,Set1[i]=Set2[i]=i;
    for (int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find(Set2,u);v=Find(Set2,v);//注意及时Find
        Add_Edge(u,v);
    }
    for (int i=1;i<=P;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find(Set2,u);v=Find(Set2,v);
        int ret=Add_Edge(u,v);
        if (ret==-1) printf("No\n");
        else printf("%d\n",ret);
    }
    return 0;
}

bool Isroot(int x)
{
    if ((S[Find(Set2,S[x].fa)].ch[0]==x)||(S[Find(Set2,S[x].fa)].ch[1]==x)) return 0;
    return 1;
}

void PushDown(int x)
{
    if (S[x].rev==1)
    {
        S[x].rev=0;
        if (S[x].ch[0]) S[S[x].ch[0]].rev^=1,swap(S[S[x].ch[0]].ch[0],S[S[x].ch[0]].ch[1]);
        if (S[x].ch[1]) S[S[x].ch[1]].rev^=1,swap(S[S[x].ch[1]].ch[0],S[S[x].ch[1]].ch[1]);
    }
    return;
}

void Rotate(int x)
{
    int y=Find(Set2,S[x].fa);int z=Find(Set2,S[y].fa);
    int sx=(x==S[y].ch[1]);
    int sy=(y==S[z].ch[1]);
    S[x].fa=z;if (Isroot(y)==0) S[z].ch[sy]=x;
    if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;S[y].ch[sx]=S[x].ch[sx^1];
    S[y].fa=x;S[x].ch[sx^1]=y;
    return;
}

void Splay(int x)
{
    int stacktop=1;Stack[1]=x;
    int now=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=Find(Set2,S[now].fa);
        now=Find(Set2,S[now].fa);
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=Find(Set2,S[x].fa);int z=Find(Set2,S[y].fa);
        if (Isroot(y)==0)
            ((S[y].ch[0]==x)^(S[z].ch[0]==y))?(Rotate(x)):(Rotate(y));
        Rotate(x);
    }
    return;
}

void Access(int x)
{
    int lastx=0;
    while (x)
    {
        Splay(x);S[x].ch[1]=lastx;S[lastx].fa=x;
        lastx=x;x=Find(Set2,S[x].fa);
    }
    return;
}

void Makeroot(int x)
{
    Access(x);Splay(x);
    S[x].rev^=1;swap(S[x].ch[0],S[x].ch[1]);
    return;
}

void Link(int x,int y)
{
    Makeroot(x);S[x].fa=y;
    return;
}

int Add_Edge(int u,int v)
{
    if (Find(Set1,u)!=Find(Set1,v))//若u,v还不在同一个联通块,则先联通
    {
        Set1[Find(Set1,u)]=Find(Set1,v);
        Link(u,v);
        return -1;
    }
    else
    {
        Makeroot(u);Access(v);Splay(v);//否则找出u,v的路径,并把整个环的信息压缩到v上
        dfs(v,v);
        S[v].ch[0]=S[v].ch[1]=0;//这里就把整棵子树丢掉了
        return Size[v];
    }
}

int Find(int *f,int x)
{
    if (f[x]!=x) f[x]=Find(f,f[x]);
    return f[x];
}

void dfs(int now,int fa)//dfs fa的子树,把所有信息全部累加到fa中,完成缩点
{
    if (now!=fa) Size[fa]+=Size[now],Set2[now]=fa;
    if (S[now].ch[0]) dfs(S[now].ch[0],fa);
    if (S[now].ch[1]) dfs(S[now].ch[1],fa);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4998]星球联盟(LCT,并查集)


HNCJ OIer