bzoj 4998 星球联盟 题解【LCT】【tarjan】

作者: wjyyy 分类: LCT,tarjan,解题报告 发布时间: 2019-01-08 16:21

点击量:27

疯狂Find()就好啦。

Description

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

你的任务是计算出,在一条新隧道建设完毕后,判断这条新轨道连接的两个星球是否属于同一个联盟,如果属于同一个联盟就计算出这个联盟中有多少个星球。

Input

第\(1\)行三个整数\(N,M\)和\(P\),分别表示总星球数,初始时太空隧道的数目和即将建设的轨道数目。

第\(2\)至第\(M+1\)行,每行两个整数,表示初始时的每条太空隧道连接的两个星球编号。

第\(M+2\)行至第\(M+P+1\)行,每行两个整数,表示新建的太空隧道连接的两个星球编号。

这些太空隧道按照输入的顺序依次建成。

\(1≤N,M,P≤200000\)

Output

输出共\(P\)行。

如果这条新的太空隧道连接的两个星球属于同一个联盟,就输出一个整数,表示这两个星球所在联盟的星球数。

如果这条新的太空隧道连接的两个星球不属于同一个联盟,就输出"No"(不含引号)。

Sample Input

5 3 4
1 2
4 3
4 5
2 3
1 3
4 5
2 4

Sample Output

No
3
2
5

HINT

题解:

看到了自己的影子……

在很久很久以前刚学tarjan缩点的时候,喜欢用一个并查集来存一个点最终属于的点,因为总感觉非简单环上的点会被缩很多次……丢人现眼的实例dfind()就是用来干这个事的……

不过这次是真的派上用场了。

这个题要把两个点所在边双连通分量(SCC)的大小求出来。当新加入一条边形成环时,就把这个环缩起来,大小为每个点大小之和(因为此时树上的点也有可能是一个SCC缩出来的),每个点的初始大小为1。缩点后原图始终是一棵树。

最重要的是缩环的细节。假设点\(u\)和点\(v\)原本就相连,我们现在又要加入一条边\((u,v)\)。那么原树上\(u\rightarrow v\)这条链上的点全部都变成了一个点,令其为\(u\)(不浪费资源)。首先split(u,v),按照我的写法,此时\(v\)在整棵树的根节点,有\(fa[v]=0\)。那么缩点之后也没有点可以成为\(u\)的父亲了,因此\(fa[u]\)也一定是\(0\)。最后更新\(sz[u]\)(子树节点大小和)为链上所有点大小之和就可以了。

\(fa[u]=0\)一定是最重要的!!!

Code:

#include<cstdio>
#include<cstring>
#define ls Find(ch[0][k])
#define rs Find(ch[1][k])
#define which(k) (ch[1][Find(fa[k])]==k)
#define isroot(k) (Find(ch[0][Find(fa[k])])!=k&&Find(ch[1][Find(fa[k])])!=k)
int ch[2][201000],fa[201000],num[201000];
int lazy[201000],sz[201000],s[201000];
int Find(int k)
{
    return (s[k]==k)?k:(s[k]=Find(s[k]));
}
void Union(int x,int y)
{
    s[Find(y)]=Find(x);
}
void pushdown(int k)
{
    if(lazy[k])
    {
        lazy[k]=0;
        lazy[ls]^=1;
        lazy[rs]^=1;
        int tmp=ls;
        ch[0][k]=rs;
        ch[1][k]=tmp;
    }
}
void maintain(int k)
{
    sz[k]=sz[ls]+num[k]+sz[rs];
}
void Rotate(int k)
{
    int y=Find(fa[k]);
    if(!isroot(y))
        ch[which(y)][Find(fa[y])]=k;
    bool d=which(k);
    fa[k]=Find(fa[y]);
    fa[y]=k;
    ch[d][y]=ch[!d][k];
    fa[ch[d][y]]=y;
    ch[!d][k]=y;
    maintain(y);
    maintain(k);
}
int stk[201000],tp=0;
void splay(int k)
{
    while(!isroot(k))
    {
        stk[++tp]=k;
        k=Find(fa[k]);
    }
    stk[++tp]=k;
    while(tp)
        pushdown(stk[tp--]);
    k=stk[1];
    while(!isroot(k))
    {
        int y=Find(fa[k]);
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)
{
    for(int x=k,y=0;x;y=x,x=Find(fa[x]))
    {
        splay(x);
        ch[1][x]=y;
        maintain(x);
    }
}
void makeroot(int k)
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
int getroot(int k)
{
    access(k);
    splay(k);
    while(ls)
        k=ls;
    return k;
}
void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
int dfs(int k,int x)
{
    int ans=num[k];
    Union(x,k);
    if(ls)
        ans+=dfs(ls,x);
    if(rs)
        ans+=dfs(rs,x);
    return ans;
}
int Link(int x,int y)
{
    x=Find(x),y=Find(y);
    int ans=0;
    makeroot(x);
    if(getroot(y)!=x)
        link(x,y);
    else
    {
        split(x,y);
        ans=dfs(y,x);
        num[x]=ans;
        maintain(x);
        fa[x]=0;
    }
    return ans;
}
int main()
{
    int n,m,p,u,v;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;++i)
        s[i]=i,num[i]=sz[i]=1;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        Link(u,v);
    }
    for(int i=1;i<=p;++i)
    {
        scanf("%d%d",&u,&v);
        int tmp=Link(u,v);
        if(tmp)
            printf("%d\n",tmp);
        else
            puts("No");
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */