题意理解花了点时间
给出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; }