动态连通块

第一行两个整数n,m，分别表示点的个数和操作的个数。
第二行n个整数，第i个整数描述第i个点的颜色，0表示白色，1表示黑色。
接下来m行，每行包含2个或者3个整数，描述三种操作。
操作1：1,x,y，表示在x,y之间加入一条边。
操作2：2,x，若x=0，询问白连通块的个数，否则询问黑连通块的个数。
操作3：3,x,y，表示第三种操作。
$n,m \leq 50000, x,y \leq n$

C++14(g++5.4) 解法, 执行用时: 458ms, 内存消耗: 143608K, 提交时间: 2019-02-09 11:05:10

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int n,m,ans1,ans0,tot0,tot1;
bool mp[maxn];
int tot;
int fa[maxn];
bitset<maxn>f[maxn],g;
int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void add(int u,int v)
{
	if(mp[u]==mp[v]){
		u=find(u);
		v=find(v);
		if(u!=v){
			fa[u]=v;
			f[v]|=f[u];
			if(mp[u]) --ans1;
			else --ans0;
		}
	}
	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){
		printf("-1\n");
		return;
	}
	g=f[u]&f[v];
	printf("%d\n",g.count());
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) {
		cin>>mp[i];	
		fa[i]=i;
		if(mp[i]) ++ans1,++tot1;
		else ++ans0,++tot0;
	}
	int s,x,y;
	while(m--)
	{
		cin>>s;
		if(s==1){
			cin>>x>>y;
			add(x,y);
		}
		else if(s==2){
			cin>>x;
			query1(x);
		}
		else{
			cin>>x>>y;
			query2(x,y);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 233ms, 内存消耗: 143828K, 提交时间: 2019-03-20 03:38:25

#include<bits/stdc++.h>
using namespace std;const int N=5e4+7;
bitset<N> bit[N];int n,m,i,j,k,num[N],col[N],fa[N],op,x,y,z;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;++i)fa[i]=i,scanf("%d",col+i),num[col[i]]++;
	for(;m--;){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d",&x,&y);
			if(col[x]==col[y]){
				if(find(x)!=find(y))bit[find(y)]|=bit[find(x)],fa[find(x)]=find(y),num[col[x]]--;
			}
			else bit[find(x)][y]=bit[find(y)][x]=1;
		}
		if(op==2)scanf("%d",&x),printf("%d\n",num[x]);
		if(op==3)scanf("%d%d",&x,&y),printf("%d\n",find(x)==find(y)?-1:1*(bit[find(x)]&bit[find(y)]).count());
	}
}

详情