LinkCutTree试水之bzoj2049[Sdoi08]山洞勘测题解

• 题目大意
  一张无向图，初始时没有边，写一个程序支持动态添边、删边、查询两点是否连通。

• 题解
  用LCT维护图的连通性。看来指针还是比较慢的。

• Code

#include <cstdio>
#include <algorithm>
#define maxn 10005
using namespace std;
int n, m;
struct node
{
    bool rev;
    node *fa, *lc, *rc;
    node() { rev = false; fa = lc = rc = NULL; }
    node(bool xrev, node *xfa, node *xlc, node *xrc)
    {
        rev = xrev;
        fa = xfa; lc = xlc; rc = xrc;
    }
    void pushdown();
}*nil = new node(), *T[maxn];
void node :: pushdown()
{
    if(this == fa -> lc || this == fa -> rc)
    {
        fa -> pushdown();
    }
    if(rev)
    {
        if(lc != nil) lc -> rev ^= 1;
        if(rc != nil) rc -> rev ^= 1;
        swap(lc, rc);
        rev = false;
    }
}
void zag(node *x)
{
    node *y = x -> fa;
    y -> rc = x -> lc;
    x -> lc -> fa = y;
    x -> lc = y;
    x -> fa = y -> fa;
    if(y == y -> fa -> lc) y -> fa -> lc = x;
    else if(y == y -> fa -> rc) y -> fa -> rc = x;
    y -> fa = x;
}
void zig(node *x)
{
    node *y = x -> fa;
    y -> lc = x -> rc;
    x -> rc -> fa = y;
    x -> rc = y;
    x -> fa = y -> fa;
    if(y == y -> fa -> lc) y -> fa -> lc = x;
    else if(y == y -> fa -> rc) y -> fa -> rc = x;
    y -> fa = x;
}
void splay(node *x)
{
    node *y = nil, *z = nil;
    x -> pushdown();
    while(x == x -> fa -> lc || x == x -> fa -> rc)
    {
        y = x -> fa; z = y -> fa;
        if(x == y -> lc)
        {
            if(y == z -> lc) zig(y);
            zig(x);
        }
        else
        {
            if(y == z -> rc) zag(y);
            zag(x);
        }
    }
}
inline void access(node *x)
{
    for(node *y = nil; x != nil; x = x -> fa)
    {
        splay(x);
        x -> rc = y;
        y = x;
    }
}
inline void makeroot(node *x)
{
    access(x); splay(x); x -> rev ^= 1;
}
inline void lnk(node *x, node *y)
{
    makeroot(x);
    x -> fa = y;
}
inline void cut(node *x, node *y)
{
    makeroot(x);
    access(y); splay(y);
    x -> fa = y -> lc = nil;
}
inline node *find(node *x)
{
    access(x);
    splay(x);
    while(x -> lc != nil) x = x -> lc;
    return x;
}
inline void read(int &a)
{
    char ch = getchar(); a = 0;
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        a = a * 10 + ch - 48;
        ch = getchar();
    }
}
int main()
{
    char opt[10];
    int a, b;
    read(n); read(m);
    *nil = node(false, nil, nil, nil);
    for(int i = 1; i <= n; ++i) T[i] = new node(false, nil, nil, nil);
    while(m--)
    {
        scanf("%s", opt);
        read(a); read(b);
        switch(opt[0])
        {
            case 'C': lnk(T[a], T[b]);
                      break;
            case 'D': cut(T[a], T[b]);
                      break;
            case 'Q': if(find(T[a]) == find(T[b])) puts("Yes");
                      else puts("No");
                      break;
            default : break;
        }
    }
    return 0;
}