bzoj 4998 星球联盟

星球联盟"/>

bzoj 4998 星球联盟

新技能 get √ ：LCT 维护边双连通分量

这题题意就是动态加边，每次求边的两端是否在一个边双连通分量里，输出 "No" 或者边双连通分量的大小

可以用两个并查集分别记录连通性和双连通性，如果还没连通就是 "No" 并在 LCT 上连边，否则直接把这条链 split 出来查即可

注意 LCT 维护的是双连通分量，所以每次跳 fa 的时候不再是 fa，而是 fa 所在的双连通分量

#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {int x = 0,f = 1; char ch = getchar();for(; !isdigit(ch); ch = getchar())if(ch == '-') f = -f;for(; isdigit(ch); ch = getchar())x = 10 * x + ch - '0';return x * f;
}
const int maxn = 200010;
int par[maxn], par2[maxn], size[maxn], ans;
inline int find(int x) {return x == par[x] ? x : par[x] = find(par[x]);}
inline int find2(int x) {return x == par2[x] ? x : par2[x] = find2(par2[x]);}
int n, m, p;
#define ls ch[x][0]
#define rs ch[x][1]
int ch[maxn][2], fa[maxn], rev[maxn], st[maxn], top;
inline int isroot(int x) { return ch[find(fa[x])][0] != x && ch[find(fa[x])][1] != x; }
inline void pushdown(int x) {if(rev[x]) {swap(ls, rs); if(ls) rev[ls] ^= 1; if(rs) rev[rs] ^= 1;rev[x] = 0;}
}
inline void rotate(int x) {int y = find(fa[x]), z = find(fa[y]);int l = (ch[y][1] == x), r = l ^ 1;if(!isroot(y)) ch[z][ch[z][1] == y] = x;fa[x] = z; fa[ch[x][r]] = y; fa[y] = x;ch[y][l] = ch[x][r]; ch[x][r] = y;
}
inline void splay(int x) {st[top = 1] = x;for(int i=x;!isroot(i);i=find(fa[i])) st[++top] = find(fa[i]);for(int i=top;i;i--) pushdown(st[i]);//PUSHDOWN(x);//cout << x << endl;while(!isroot(x)) {int y = find(fa[x]), z = find(fa[y]);if(!isroot(y)) {if(ch[z][0] == y ^ ch[y][0] == x) rotate(x);else rotate(y);} rotate(x);}
}
inline void access(int x) {for(int y = 0; x; splay(x), rs = y, y = x, x = find(fa[x]));
}
inline void makeroot(int x) {access(x); splay(x); rev[x] ^= 1;
}
inline void link(int x, int y) {makeroot(x); fa[x] = y;
}
void dfs(int x, int pre) {if(!x) return;ans += size[x];if(x != pre) size[pre] += size[x], par[x] = pre;dfs(ls, pre); dfs(rs, pre);
}
inline void lnk(int u, int v) {ans = 0;if(find2(u) != find2(v)) {par2[par2[u]] = par2[v];//cout << u << " " << v << endl;
        link(u, v);}else {makeroot(u); access(v); splay(v); dfs(v, v);}
}
int main() {n = read(), m = read(), p = read();rep(i, 1, n) size[i] = 1, par[i] = i, par2[i] = i;rep(i, 1, m) {int u = find(read()), v = find(read());lnk(u, v);}rep(i, 1, p) {int u = find(read()), v = find(read()); lnk(u, v);printf(ans ? "%d\n" : "No\n", ans);}
}

转载于:.html