维护一片森林, 支持Connect, Destroy和查询连通性. 点数n≤10000, 操作数m≤200000. 最近写的第一道LCT.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4;
struct Node {
Node* ch[2], * fa;
bool rev;
int t;
Node();
void setf(int t1, Node* f)
{
t = t1;
fa = f;
t >= 0 ? f->ch[t] = this : 0;
}
void reverse()
{
rev = !rev;
swap(ch[0], ch[1]);
ch[0]->t = 0;
ch[1]->t = 1;
}
void down()
{
if (rev) {
ch[0]->reverse();
ch[1]->reverse();
rev = false;
}
}
} nodes[MAX_N + 1], * nil = nodes;
Node::Node(): fa(nil), rev(false), t(-1) { ch[0] = ch[1] = nil; }
inline void rot(Node* y)
{
Node* x = y->fa;
int t = y->t;
y->setf(x->t, x->fa);
y->ch[t^1]->setf(t, x);
x->setf(t^1, y);
}
void splay(Node* x)
{
Node* y;
int top = 0;
static Node* S[MAX_N];
for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
for (y->down(); top; S[--top]->down()) ;
while (x->t >= 0) {
if ((y = x->fa)->t >= 0)
rot(x->t ^ y->t ? x : y);
rot(x);
}
}
inline void access(Node* x)
{
for (Node* y = nil; x != nil; y = x, x = x->fa) {
splay(x);
x->ch[1]->t = -1;
y->setf(1, x);
}
}
inline void make_root(Node* x)
{
access(x);
splay(x);
x->reverse();
}
inline void link(Node* x, Node* y)
{
make_root(x);
x->setf(-1, y);
}
inline void cut(Node* x, Node* y)
{
make_root(y);
access(x);
splay(x);
x->ch[0] = y->fa = nil;
y->t = -1;
}
inline Node* find_root(Node* x)
{
access(x);
splay(x);
while (x->ch[0] != nil) {
x = x->ch[0];
x->down();
}
return x;
}
int main()
{
int n, m, u, v;
char s[8];
scanf("%d%d", &n, &m);
while (m--) {
scanf("%s%d%d", s, &u, &v);
Node* x = nodes + u, * y = nodes + v;
switch (s[0]) {
case 'Q':
puts(find_root(x) == find_root(y) ? "Yes" : "No"); break;
case 'C':
link(x, y); break;
default:
cut(x, y);
}
}
return 0;
}