[题解]bzoj2049(SDOI2008)Cave 洞穴勘探

本文主要是介绍[题解]bzoj2049(SDOI2008)Cave 洞穴勘探，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

        这一题是LCT的模板题，初学者可以练练手，只需要学会基础的link和cut操作就可以完成。（听说用不压缩路径的并查集在某些数据较水的OJ可以AC）

代码：

#include<cstdio>
#include<algorithm>
using namespace std;const int maxn=10010;
struct node{int fa,ch[2];bool reverse,is_root;
}T[maxn];
int n,m;void pushreverse(int x){if(!x)return;swap(T[x].ch[0],T[x].ch[1]);T[x].reverse^=1;
}
void pushdown(int x){if(T[x].reverse){pushreverse(T[x].ch[0]);pushreverse(T[x].ch[1]);T[x].reverse=false;}
}
int getson(int x){return x==T[T[x].fa].ch[1];
}
void rotate(int x){if(T[x].is_root)return;int k=getson(x),fa=T[x].fa;int fafa=T[fa].fa;T[fa].ch[k]=T[x].ch[k^1];if(T[x].ch[k^1])T[T[x].ch[k^1]].fa=fa;T[x].ch[k^1]=fa;T[fa].fa=x;T[x].fa=fafa;if(!T[fa].is_root)T[fafa].ch[fa==T[fafa].ch[1]]=x;else T[x].is_root=true,T[fa].is_root=false;
}
void push(int x){if(!T[x].is_root)push(T[x].fa);pushdown(x);
}
void Splay(int x){push(x);for(int fa;!T[x].is_root;rotate(x)){if(!T[fa=T[x].fa].is_root){rotate((getson(x)==getson(fa))?fa:x);}}
}
void access(int x){int y=0;do{Splay(x);T[T[x].ch[1]].is_root=true;T[T[x].ch[1]=y].is_root=false;x=T[y=x].fa;}while(x);
}
bool judge(int u,int v){while(T[u].fa)u=T[u].fa;while(T[v].fa)v=T[v].fa;return u==v;
}
void mroot(int x){access(x);Splay(x);pushreverse(x);
}
void link(int u,int v){mroot(u);T[u].fa=v;
}
void cut(int u,int v){mroot(u);Splay(v);T[T[v].ch[0]].fa=T[v].fa;T[T[v].ch[0]].is_root=true;T[v].fa=0;T[v].ch[0]=0;
}
void Work(){char opt[50];int u,v;while(m--){scanf("%s%d%d",opt,&u,&v);if(opt[0]=='Q'){if(judge(u,v))printf("Yes\n");else printf("No\n");}else if(opt[0]=='C'){link(u,v);}else if(opt[0]=='D'){cut(u,v);}}
}int main(){scanf("%d%d\n",&n,&m);for(int i=1;i<=n;i++){T[i].reverse=T[i].fa=T[i].ch[0]=T[i].ch[1]=0;T[i].is_root=true;}Work();return 0;
}

这篇关于[题解]bzoj2049(SDOI2008)Cave 洞穴勘探的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---