bzoj4998 星球联盟

2018-09-08 20:57:19


题意:给出一个无向图,有p条待添加的边

两个点连通的定义为:它们之间有两条互不相交的路径(即环形路径)

对于每一次添加边,若这两个点连通,输出连通块的大小,否则输出 $No$


连通性显然可以用并查集维护

这里连通的定义是两条路径,所以开两个并查集。

用并查集找环,找到之后在LCT上把它缩成一个点

就是 $access$ 操作与以往不同

inline void access(int x)
{
    for (reg int y=0;x;)
    {
        splay(x); rs=y; f[y]=x; y=x; x=find(f[x]);
    }
}

注意x要跳到它父亲节点所在连通块的根节点

完整代码如下:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ls ch[x][0]
#define rs ch[x][1]
#define reg register
using namespace std;
const int N=2e5+5;
int n,m,T,ch[N][2],f[N],fa[N],fh[N],tot[N],ans,stack[N];
bool r[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int Find(int x){return fh[x]==x?x:fh[x]=Find(fh[x]);}
inline bool isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}
inline int get(int x){return ch[f[x]][1]==x;}
inline void rev(int x){swap(ls,rs); r[x]^=1;}
inline void pushdown(int x)
{
    if (!r[x]) return;
    if (ls) rev(ls);
    if (rs) rev(rs);
    r[x]=0;
}
inline void rotate(int x)
{
    int y=f[x],z=f[y],k=get(x),w=ch[x][k^1];
    if (!isroot(y)) ch[z][get(y)]=x;
    ch[x][k^1]=y; ch[y][k]=w;
    if (w) f[w]=y; f[y]=x; f[x]=z;
}
inline void splay(int x)
{
    int y=x,z,top=0;
    stack[++top]=y;
    while (!isroot(y)) stack[++top]=y=f[y];
    while (top) pushdown(stack[top--]);
    while (!isroot(x))
    {
        y=f[x],z=f[y];
        if (!isroot(y)) rotate(get(x)^get(y)?x:y);
        rotate(x);
    }
}
inline void access(int x)
{
    for (reg int y=0;x;)
    {
        splay(x); rs=y; f[y]=x; y=x; x=find(f[x]);
    }
}
inline void makeroot(int x)
{
    access(x); splay(x); rev(x);
}
inline void split(int x,int y)
{
    makeroot(x); access(y); splay(y);
}
inline void link(int x,int y)
{
    makeroot(x); f[x]=y;
}
void dfs(int x,int pre)
{
    if (!x) return; ans+=tot[x];
    if (x!=pre) fa[x]=pre,tot[pre]+=tot[x];
    dfs(ls,pre); dfs(rs,pre);
}
inline void add(int x,int y)
{
    ans=0;
    if (Find(x)!=Find(y)) fh[fh[x]]=fh[y],link(x,y);
    else split(x,y),dfs(y,y),ch[y][0]=ch[y][1]=0;
}
int main()
{
    n=read(),m=read(),T=read();
    for (reg int i=1;i<=n;i++) fa[i]=fh[i]=i,tot[i]=1;
    for (reg int i=1,x,y;i<=m;i++) x=find(read()),y=find(read()),add(x,y);
    while (T--)
    {
        int x=find(read()),y=find(read()); add(x,y);
        if (!ans) puts("No"); else printf("%d\n",ans);
    }
    return 0;
}