百度网站是百度公司做的吗,东莞网页设计,海南百度竞价排名,外贸平台排名洞穴勘测
luogu 2147
金牌导航 LCT-1
题目大意
给你若干操作#xff0c;有三种操作#xff1a; 1.连接两个点 2.吧两个点之间的连边断掉#xff08;保证有这条边#xff09; 3.查询两个点之间是否连通
样例 #1
输入样例 #1
200 5
Query 123 127
Connect 123 127
Que…洞穴勘测
luogu 2147
金牌导航 LCT-1
题目大意
给你若干操作有三种操作 1.连接两个点 2.吧两个点之间的连边断掉保证有这条边 3.查询两个点之间是否连通
样例 #1
输入样例 #1
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127输出样例 #1
No
Yes
No样例#2
输入样例 #2
3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3输出样例 #2
Yes
No数据范围
1⩽n⩽104,m⩽2×1051\leqslant n\leqslant 10^4, m\leqslant 2\times 10^51⩽n⩽104,m⩽2×105
解题思路
在LCT上建出相应的图每次查询判断根节点是否相同即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 10010
using namespace std;
int n, m, x, y, top, p[N], d[N], fa[N], son[N][2];
string str;
bool IR(int x)//LCT模板
{if (!fa[x]) return true;return son[fa[x]][0] ! x son[fa[x]][1] ! x;
}
void down(int x)
{if (p[x] x){swap(son[x][0], son[x][1]);p[son[x][0]] ^ 1;p[son[x][1]] ^ 1;p[x] 0;}return;
}
bool ILS(int x)
{return x son[fa[x]][0];
}
int which(int x)
{return x son[fa[x]][1];
}
void rotate(int x)
{int y fa[x], z fa[y], k !ILS(x), g son[x][!k];if (!IR(y)) son[z][!ILS(y)] x;son[x][!k] y;son[y][k] g;if (g) fa[g] y;fa[x] z;fa[y] x;return;
}
void Splay(int x)
{d[top 1] x;for (int i x; !IR(i); i fa[i]) d[top] fa[i];while(top) down(d[top--]);while(!IR(x)){if (!IR(fa[x])){if (ILS(x) ILS(fa[x])) rotate(fa[x]);else rotate(x);}rotate(x);}return;
}
void access(int x)
{for (int y 0; x; y x, x fa[x]) Splay(x), son[x][1] y;return;
}
void make_root(int x)
{access(x);Splay(x);p[x] ^ 1;return;
}
int find_root(int x)
{access(x);Splay(x);down(x);while(son[x][0]) x son[x][0], down(x);Splay(x);return x;
}
void link(int x, int y)
{make_root(x);fa[x] y;return;
}
void cut(int x, int y)
{make_root(x);access(y);Splay(y);son[y][0] 0;fa[x] 0;return;
}
int main()
{scanf(%d%d, n, m);while(m--){cinstr;scanf(%d%d, x, y);if (str Connect) link(x, y);else if (str Destroy) cut(x, y);else if (find_root(x) find_root(y)) puts(Yes);//判断根节点是否相同else puts(No); }return 0;
}
