题意概述: 给出 N 个点, 一开始不连通, M 次操作, 删边加边, 保证图是一个森林, 询问两点连通性
N<=10000,M<=200000
实际上我就是想来放个 LCT 板子
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- #include<cmath>
- #include<queue>
- #include<set>
- #include<map>
- #include<vector>
- #include<cctype>
- using namespace std;
- int N,M;
- struct link_cut_tree{
- static const int maxn=100005;
- struct node{
- int ch[2],fa; bool res;
- node(){ ch[0]=ch[1]=fa=0,res=0; }
- }nd[maxn];
- void init(int n) { for(int i=1;i<=n;i++) nd[i].ch[0]=nd[i].ch[1]=nd[i].fa=0,nd[i].res=0; }
- void link(int x,int d,int y) { nd[x].ch[d]=y,nd[y].fa=x; }
- bool isrt(int x) { return nd[nd[x].fa].ch[0]!=x&&nd[nd[x].fa].ch[1]!=x; }
- void pushdown(int x)
- {
- if(!nd[x].res) return;
- int lc=nd[x].ch[0],rc=nd[x].ch[1];
- if(lc) nd[lc].res^=1,swap(nd[lc].ch[0],nd[lc].ch[1]);
- if(rc) nd[rc].res^=1,swap(nd[rc].ch[0],nd[rc].ch[1]);
- nd[x].res=0;
- }
- void rot(int x)
- {
- int y=nd[x].fa,z=nd[y].fa;
- pushdown(y);pushdown(x);
- if(!isrt(y)) link(z,nd[z].ch[1]==y,x); nd[x].fa=z;
- int d=nd[y].ch[0]==x;
- link(y,d^1,nd[x].ch[d]);
- link(x,d,y);
- }
- void splay(int x)
- {
- pushdown(x);
- while(!isrt(x)){
- int y=nd[x].fa,z=nd[y].fa;
- if(!isrt(y)) rot((nd[y].ch[0]==x)==(nd[z].ch[0]==y)?y:x);
- rot(x);
- }
- }
- void access(int x)
- {
- int y=0;
- while(x){ splay(x); nd[x].ch[1]=y,y=x,x=nd[x].fa; }
- }
- void mroot(int x)
- {
- access(x); splay(x);
- nd[x].res^=1,swap(nd[x].ch[0],nd[x].ch[1]);
- }
- void Link(int x,int y) { mroot(x); nd[x].fa=y; }
- void Cut(int x,int y)
- {
- mroot(x); access(y); splay(y);
- nd[x].fa=nd[y].ch[0]=0;
- }
- int find(int x)
- {
- access(x); splay(x);
- while(nd[x].ch[0]){ pushdown(nd[x].ch[0]); x=nd[x].ch[0]; }
- return x;
- }
- }lct;
- void work()
- {
- scanf("%d%d",&N,&M);
- char op[10]; int x,y;
- for(int i=1;i<=M;i++){
- scanf("%s%d%d",op,&x,&y);
- if(op[0]==C) lct.Link(x,y);
- else if(op[0]==D) lct.Cut(x,y);
- else if(op[0]==Q) puts(lct.find(x)==lct.find(y)?"Yes":"No");
- }
- }
- int main()
- {
- work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2511502.html