P10657 BZOJ4998 星球联盟
大意
动态维护边双连通分量的大小。
思路
由于是动态的维护边双，我们可以用 LCT 维护。
但是我们的 LCT 无法处理与环有关的问题，我们采用并查集协助维护。具体来说，我们用数组 \(f\) 来维护缩点，\(f[i]\) 就代表点 \(i\) 所属的边双连通的代表元。所有在涉及有关 LCT 操作的时候，我们的 \(fa(x)\) 都要写成 \(find(fa(x))\)，这是一个易错点。
特别的，我们的连边函数发生了变化，如果不成环，那就无所谓，还是按照原来的方式，如果是成环了，那就直接提取 \(x \to y\) 的路径，通过递归暴力缩点，由于每个点只会被缩一次，所以均摊复杂度很低。
在暴力缩点的过程中，我们可以用一个数组记录缩点后该边双连通分量的大小，这样就可以知道联盟的大小了。
代码
#include<iostream>
using namespace std;#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 2 * 1e5 + 5;
struct node{int ch[2], fa, sz;bool tag;
}t[MAXN];int f[MAXN], cnt[MAXN];int fd(int x){return (x == f[x]) ? x : f[x] = fd(f[x]);
}bool isroot(int x){int fx = fd(fa(x));return (lc(fx) != x) && (rc(fx) != x);
}void pushup(int x){t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
}void update(int x){if(!x) return;swap(lc(x), rc(x));t[x].tag ^= 1;
}void pushdown(int x){if(t[x].tag){update(lc(x));update(rc(x));t[x].tag = 0;}
}void rotate(int x){int y = fd(fa(x)), z = fd(fa(y));int k = (rc(y) == x);if(!isroot(y)){t[z].ch[rc(z) == y] = x;}fa(x) = z;t[y].ch[k] = t[x].ch[k ^ 1];if(t[x].ch[k ^ 1]){fa(t[x].ch[k ^ 1]) = y;}t[x].ch[k ^ 1] = y;fa(y) = x;
}void pushshell(int x){if(!isroot(x)){pushshell(fd(fa(x)));}pushdown(x);
}void splay(int x){x = fd(x);pushshell(x);while(!isroot(x)){int y = fd(fa(x)), z = fd(fa(y));if(!isroot(y)){(rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);}rotate(x);}
}void access(int x){for(int y = 0;x;y = x, x = fd(fa(x))){splay(x);rc(x) = y;}
}void makeroot(int x){x = fd(x);access(x);splay(x);update(x);
}void split(int x, int y){makeroot(x);access(y);splay(y);
}int fdrt(int x){access(x);splay(x);while(lc(x)){pushdown(x);x = lc(x);}splay(x);return x;
}void merge(int x, int rt){if(!x) return;f[fd(x)] = fd(rt);if(x != rt) cnt[rt] += cnt[x];merge(lc(x), rt);merge(rc(x), rt);lc(x) = rc(x) = 0;
}bool link(int x, int y){x = fd(x), y = fd(y);if(x == y) return true;if(fdrt(x) != fdrt(y)){makeroot(x);fa(x) = y;return false;}else{split(x, y);merge(lc(y), y);return true;}
}int main(){int n, m, p;scanf("%d %d %d", &n, &m, &p);for(int i = 1;i <= n;i ++){f[i] = i;cnt[i] = 1;}for(int i = 0;i < m;i ++){int u, v;scanf("%d %d", &u, &v);link(u, v);}for(int i = 0;i < p;i ++){int u, v;scanf("%d %d", &u, &v);if(link(u, v)){printf("%d\n", cnt[fd(u)]);}else{printf("No\n");}}return 0;
}