[LOJ#121]动态图连通性
试题描述
这是一道模板题。
你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。
- 0：加入一条边。保证它不存在。
- 1：删除一条边。保证它存在。
- 2：查询两个点是否联通。
输入
输入的第一行是两个数 N M。N=5000,M≤500000。
接下来 M 行，每一行三个数 op x y。 op 表示操作编号。
输出
对于每一个 op=2 的询问，输出一行
Y 或 N ，表示两个节点是否连通。输入示例1
200 5 2 123 127 0 123 127 2 123 127 1 127 123 2 123 127
输出示例1
N
Y
N
输入示例2
4 10 0 1 2 0 2 3 0 3 1 2 1 4 0 4 3 2 1 4 1 2 3 2 1 4 1 1 3 2 1 4
输出示例2
N
Y
Y
N
数据规模及约定
对于数据点 1，N≤200,M≤200
对于数据点 2，N=5,M≤30
对于数据点 3，N=10,M≤1000，其中查询的次数 >=900 次。
对于数据点 4，N=300,M≤50000
对于数据点 5，N=5000,M≤200000，没有操作 1，其中约70是操作2。
对于数据点 6，N=5000,M≤200000，没有操作 1，其中约70是操作0。
对于数据点 7、8，N=100,M≤500000
对于数据点 9，N=5000,M≤500000，图是一棵树，其直径 ≤6 。
对于数据点 10， N=5000,M≤500000，图是一棵树，其每个点度数 ≤4 。
P.S. 其实 9 是菊花，10 是单链，而没有放随机树的点...
题解
动态树模板练习。（离线，维护删除时间最大生成树）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 505010
#define oo 2147483647
struct Node {
int siz, tim, mni;
bool rev;
Node(): rev(0) {}
Node(int _): tim(_) {}
};
struct LCT {
Node ns[maxn];
int ch[maxn][2], fa[maxn];
int S[maxn], top;
int _siz, _mni;
bool isrt(int u) { return !fa[u] || (ch[fa[u]][0] != u && ch[fa[u]][1] != u); }
void pushdown(int o) {
if(!ns[o].rev) return ;
swap(ch[o][0], ch[o][1]);
for(int i = 0; i < 2; i++) if(ch[o][i]) ns[ch[o][i]].rev ^= 1;
ns[o].rev = 0;
return ;
}
void maintain(int o) {
ns[o].siz = 1; ns[o].mni = o;
for(int i = 0; i < 2; i++) if(ch[o][i]) {
ns[o].siz += ns[ch[o][i]].siz;
int& tmp = ns[o].mni;
if(ns[tmp].tim > ns[ns[ch[o][i]].mni].tim) tmp = ns[ch[o][i]].mni;
}
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(!isrt(y)) ch[z][ch[z][1]==y] = u;
if(ch[y][1] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;
ch[y][l] = ch[u][r]; ch[u][r] = y;
maintain(y);
return ;
}
void splay(int u) {
int t = u; S[top = 1] = t;
while(!isrt(t)) S[++top] = fa[t], t = fa[t];
while(top) pushdown(S[top--]);
while(!isrt(u)) {
int y = fa[u], z = fa[y];
if(!isrt(y)) {
if(ch[y][0] == u ^ ch[z][0] == y) rotate(u);
else rotate(y);
}
rotate(u);
}
return maintain(u);
}
void access(int u) {
splay(u); ch[u][1] = 0; maintain(u);
while(fa[u]) splay(fa[u]), ch[fa[u]][1] = u, maintain(fa[u]), splay(u);
return ;
}
void makert(int u) {
access(u); ns[u].rev ^= 1;
return ;
}
void link(int a, int b) {
// printf("link(%d, %d)
", a, b);
makert(b); fa[b] = a;
return ;
}
void cut(int a, int b) {
// printf("cut(%d, %d)
", a, b);
makert(a); access(b); ch[b][0] = fa[a] = 0;
return maintain(b);
}
void query(int a, int b) {
// printf("query(%d, %d)
", a, b);
makert(b); access(a);
_siz = ns[a].siz; _mni = ns[a].mni;
return ;
}
bool together(int a, int b) {
// printf("together(%d, %d)
", a, b);
if(a == b) return 1;
makert(b); access(a);
bool ok = 0;
while(ch[a][0]) {
a = ch[a][0];
if(a == b){ ok = 1; break; }
}
splay(a);
return ok;
}
} sol;
#define pii pair <int, int>
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
struct Que {
int tp, a, b, e;
Que() {}
Que(int _1, int _2, int _3): tp(_1), a(_2), b(_3) {}
} qs[maxn];
pii edges[maxn];
int uid[25010010];
int lstdel[maxn], cntn;
int code(pii e) { return e.x * 5001 + e.y; }
int main() {
int n = cntn = read(), m = read();
for(int i = 1; i <= m; i++) {
int tp = read(), a = read(), b = read();
if(a > b) swap(a, b);
qs[i] = Que(tp, a, b);
}
for(int i = m; i; i--) {
int tp = qs[i].tp, a = qs[i].a, b = qs[i].b;
if(tp == 1) {
pii e = mp(a, b);
lstdel[qs[i].e = uid[code(e)] = ++cntn] = i;
edges[cntn] = e;
}
if(tp == 0) {
pii e = mp(a, b);
if(uid[code(e)]) qs[i].e = uid[code(e)], uid[code(e)] = 0;
else lstdel[qs[i].e = ++cntn] = m + 1, edges[cntn] = e;
}
}
for(int i = 1; i <= n; i++) sol.ns[i] = Node(oo);
for(int i = n + 1; i <= cntn; i++) sol.ns[i] = Node(lstdel[i]);
for(int i = 1; i <= m; i++) {
int tp = qs[i].tp, a = qs[i].a, b = qs[i].b, e = qs[i].e;
if(tp == 0) {
if(!sol.together(a, b)) sol.link(a, e), sol.link(e, b);
else {
sol.query(a, b);
if(lstdel[sol._mni] < lstdel[e]) {
sol.cut(edges[sol._mni].x, sol._mni);
sol.cut(sol._mni, edges[sol._mni].y);
sol.link(a, e); sol.link(e, b);
}
}
}
if(tp == 1) {
sol.query(a, b);
if(sol._siz == 3) sol.cut(a, e), sol.cut(b, e);
}
if(tp == 2) puts(sol.together(a, b) ? "Y" : "N");
}
return 0;
}