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

点击量：236

疯狂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;
}