题面
bzoj
题解
bzoj2959: 长跑 https://www.cnblogs.com/zzy2005/p/10324298.html 的弱化版
产生了环就并查集维护一下
- Code
- #include<bits/stdc++.h>
- #define LL long long
- #define RG register
- using 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;
- }
来源: http://www.bubuko.com/infodetail-3003244.html