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

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

并查集 $+ b i t s e t$ 优化。

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

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

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

复杂度 $O\left(\begin{array}{l}n^{2} \\ W\end{array}\right), \quad \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;
}