出题人题解 | #动态连通块#

原题解链接：https://ac.nowcoder.com/discuss/153563

并查集$+bitset+bitset$优化。

操作二可以在加边的过程中求出。即加入一条端点同色的边，并查集判断是否可以消去一个白（黑）连通块。

操作三求的是$x,yx,y$所在的两个白连通块都连出的黑点（假设$x,yx,y$是白色，黑色的情况是一样的）。

于是可以$bitsetbitset$维护每个白联通块连出的黑点，黑连通块连出的白点。每加入一条端点异色的边，在两个白、黑连通块的$bitsetbitset$中将一个位置设为$11$；加入一条端点同色的边，就是合并白（黑）连通块的过程，同时合并两个白（黑）连通块的$bitsetbitset$。

复杂度 $O\left(\begin{array}{c}{n}^2\\ W\end{array}\right),\mathrm{W}=32O\backslash left(\backslash begin\{array\}\{l\}n^\{2\}\; \backslash \backslash \; W\backslash end\{array\}\backslash right),\; \backslash quad\; \backslash mathrm\{W\}=32$ 或 64

#include<cstdio>
#include<iostream>
#include<bitset>
using namespace std;

const int N = 50005;
bitset<N> f[N], g;
int fa[N], col[N], ans0, ans1, tot0, tot1;

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void add(int u,int v) {
    if (col[u] == col[v]) {
        u = find(u), v = find(v);
        if (u != v) {
            fa[u] = v;
            f[v] |= f[u];
            if (col[u] == 0) ans0 --;
            else ans1 --;
        }
    }
    else {
		int t1 = find(u), t2 = find(v);
        f[t1].set(v);
        f[t2].set(u);
    }
}
void query1(int x) {
    printf("%d\n", x == 0 ? ans0 : ans1);
}
void query2(int u,int v) {
    u = find(u), v = find(v);
    if (u == v) { 
    	puts("-1");
        return ; 
    }
    g = f[u] & f[v];
    printf("%d\n", g.count());
}
int main() {
    int n, Q, opt, a, b;
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; ++i) {
    	scanf("%d", &col[i]);
    	fa[i] = i;
    	if (col[i] == 0) ans0 ++, tot0 ++;
    	else ans1 ++, tot1 ++;
	}
    while (Q --) {
        scanf("%d", &opt);
        if (opt == 1) {
        	scanf("%d%d", &a, &b);
        	add(a, b);
		}
        else if (opt == 2) {
        	scanf("%d", &a);
        	query1(a);
		}
        else if (opt == 3) {
        	scanf("%d%d", &a, &b);
        	query2(a, b);
		}
    }
    return 0;
}