本文共 1174 字，大约阅读时间需要 3 分钟。

【题目】

【题解】

题意：连通块的意思是颜色相同且互相之间可以连通的点集。操作有三种： 1、在两个点之间连一条边。2、询问白（黑）连通块个数。3、给出x,y两个相同颜色的点，询问存在多少个异色的点，将它改变颜色后，x,y所在的连通块会合并为一个。如果x,y已经在一个连通块内了，输出-1。

思路：用并查集判断连一条边是不是要合并连通块，用bitset维护每个白联通块连出的黑点，黑连通块连出的白点，暴力跑一遍就好了。

【代码】

#include 
   
    using namespace std;const int maxn=50005;bitset 
    
      f[maxn],g;int pre[maxn],col[maxn];int ans[2]={0}; //连通块个数计数int Find(int x){    return x==pre[x]? x : pre[x]=Find(pre[x]);}void add(int u,int v) //在两个点之间连一条边{    int a=Find(u),b=Find(v);    if(col[u]==col[v])    {        if(a!=b)        {            pre[a]=b;            f[b]|=f[a]; //取a b并集给b            ans[col[a]]--;        }    }    else f[a].set(v),f[b].set(u);}void query(int u,int v){    u=Find(u),v=Find(v);    if(u==v)    {    	puts("-1"); return ;    }    g=f[u]&f[v]; //取a b交集给g    printf("%d\n",g.count());}int main(){    int n,m; scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {    	scanf("%d",&col[i]);    	pre[i]=i;    	ans[col[i]]++;	}    while(m--)    {        int opt,a,b; scanf("%d%d",&opt,&a);        if(opt==1) scanf("%d",&b),add(a,b);        else if(opt==2) printf("%d\n",ans[a]);        else if(opt==3) scanf("%d",&b),query(a,b);    }    return 0;}
    
   

转载地址：http://ybben.baihongyu.com/