题意理解花了点时间
给出x,y两个点,保证同色(为了方便描述,x,y都是白点,黑色同理)。询问存在多少个黑点,将它改变颜色后,x,y所在的白连通块会合并为一个。
貌似隐含了x,y必定在同一个不分颜色的连通块,不然如果没有边相连岂不是无解?
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N=5e4+5;
int n,m,col[N],fa[N],num[2];bitset<N>S[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=gi();m=gi();
for(int i=1;i<=n;++i)++num[col[i]=gi()],fa[i]=i;
while(m--){
int op=gi(),x=gi(),y;if(op&1)y=gi();
if(op==1)
if(col[x]^col[y])S[find(x)][y]=1,S[find(y)][x]=1;
else{
x=find(x),y=find(y);
if(x^y)fa[y]=x,S[x]|=S[y],--num[col[x]];
}
if(op==2)
printf("%d\n",x?num[1]:num[0]);
if(op==3)
printf("%d\n",find(x)^find(y)?(int)(S[find(x)]&S[find(y)]).count():-1);
}
return 0;
} 


京公网安备 11010502036488号