[LOJ#121]动态图连通性

[LOJ#121]动态图连通性

试题描述

这是一道模板题。

你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。

• 0：加入一条边。保证它不存在。
• 1：删除一条边。保证它存在。
• 2：查询两个点是否联通。

输入

输入的第一行是两个数 N M。N=5000,M≤500000。

接下来 M 行，每一行三个数 op x y。 op 表示操作编号。

输出

输入示例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，其中约$\mathrm{70是操作2。}$

对于数据点 6，N=5000,M≤200000，没有操作 1，其中约$\mathrm{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 
#include 
#include 
#include 
#include 
#include 
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 2147483647struct 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)\n", a, b);makert(b); fa[b] = a;return ;}void cut(int a, int b) {
//		printf("cut(%d, %d)\n", 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)\n", 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)\n", 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 
#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;
}

转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/7190926.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！