bzoj4998: 星球联盟(link

星球联盟(link"/>

bzoj4998: 星球联盟(link

题面

bzoj

题解

bzoj2959: 长跑的弱化版

产生了环就并查集维护一下

Code

#include<bits/stdc++.h>#define LL long long
#define RG registerusing namespace std;
template<class T> inline void read(T &x) {x = 0; RG char c = getchar(); bool f = 0;while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();x = f ? -x : x;return ;
}
template<class T> inline void write(T x) {if (!x) {putchar(48);return ;}if (x < 0) x = -x, putchar('-');int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 200010;
int ch[N][2], w[N], fa[N], S[N], top, bl[N];
bool rev[N];
int find(int x) {return bl[x] == x ? x : bl[x] = find(bl[x]);
}
#define get(x) (ch[find(fa[x])][1] == x)
bool isroot(int x) {return ch[find(fa[x])][0] != x && ch[find(fa[x])][1] != x;
}
void rotate(int x) {int y = find(fa[x]), z = find(fa[y]), k = get(x);if (!isroot(y)) ch[z][get(y)] = x;fa[x] = z;ch[y][k] = ch[x][k ^ 1]; fa[ch[x][k ^ 1]] = y;ch[x][k ^ 1] = y; fa[y] = x;
}
void putrev(int x) {rev[x] ^= 1;swap(ch[x][0], ch[x][1]);
}
void pushdown(int x) {if (rev[x]) {if (ch[x][0]) putrev(ch[x][0]);if (ch[x][1]) putrev(ch[x][1]);rev[x] = 0;}
}
void splay(int x) {S[top = 1] = x;for (int i = x; !isroot(i); i = find(fa[i])) S[++top] = find(fa[i]);for (int i = top; i; i--) pushdown(S[i]);while (!isroot(x)) {int y = find(fa[x]);if (!isroot(y))(get(x) ^ get(y)) ? rotate(x) : rotate(y);rotate(x);}
}
void access(int x) { for(int y = 0; x; y = x, x = find(fa[x])) splay(x), ch[x][1] = y; }
void makeroot(int x) { access(x); splay(x); putrev(x); }
void split(int x, int y) { makeroot(x); access(y); splay(y); }
void link(int x, int y) { makeroot(x); fa[x] = y; }int pa[N];
int getf(int x) {return pa[x] == x ? x : pa[x] = getf(pa[x]);
}
void dfs(int x, int y) {w[y] += w[x];bl[x] = y;if (ch[x][0]) dfs(ch[x][0], y);if (ch[x][1]) dfs(ch[x][1], y); 
}
int main() {int n, m, p;read(n), read(m), read(p);for (int i = 1; i <= n; i++) pa[i] = bl[i] = i, w[i] = 1;for (int i = 1, u, v; i <= m; i++) {read(u), read(v);u = find(u), v = find(v);if (u == v) continue;if (getf(u) == getf(v)) {split(u, v);dfs(ch[v][0], v);continue;}pa[getf(v)] = getf(u);link(u, v);}for (int i = 1, x, y; i <= p; i++) {read(x), read(y);x = find(x), y = find(y);if (x == y) {printf("%d\n", w[x]);continue;}if (getf(x) != getf(y)) {puts("No");link(x, y);pa[getf(y)] = getf(x);continue;}split(x, y);dfs(ch[y][0], y);printf("%d\n", w[y]);}return 0;
}

转载于:.html