看到有篇Bicoloring的题解很多人转载，但是我发现这里面是有错误的，所以今天写出来提醒大家。
题目地址：Bicoloring

题意

m个查询，每个查询输入a b，表示 顶点a b之间涂色。 规定只能涂颜色0 或者颜色 1，一个节点相连的边 必须涂成相同的颜色。 问 ，输入m组 a b之后，会不会犯规。

思路

并查集： 每输入一组ａｂ查找他们的公共祖先，如果ａ　ｂ公共祖先相同判断他们到公共祖先的距离是否为偶数，如果是偶数就不是二分图，反之可以构成二分图

染色法： 给每个顶点 标记值，如果相邻两个顶点的标记值相同，说明环是奇数，不满足。

并查集

问题出现在路径压缩 , 如果你进行了路径压缩那么下次判断是他到根节点的距离就变了,会出错.
如果不进行路径压缩会超时.
但是这题的数据比较水, 进行了路径压缩还是能AC , 只能说出题人的数据不太行.
我先列一组会出错的数据吧
5
6
0 1
1 2
2 3
0 4
4 5
3 5
如果使用染色法应该输出BICOLORABLE.
但是用并查集缺输出了 NOT NICOLORABLE.

#include <iostream>
using namespace std;
int disjoint_set[210];
int find(int x,int &s)
{
if(x!=disjoint_set[x])
{
s++;
find(disjoint_set[x],s);
//压缩路径会出错，但这题数据太水，检测不到。
}
return disjoint_set[x];
}
int main()
{
int n,a,b,l;
while(scanf("%d",&n)!=EOF && n!=0)
{
bool flag = true;
scanf("%d",&l);
for(int i=0;i<n;i++)
{
disjoint_set[i] = i;
}
while(l--)
{
scanf("%d%d",&a,&b);
if(!flag) continue;
int sa=0,sb=0;
int disjoint_set_a,disjoint_set_b;
disjoint_set_a = find(a,sa);
disjoint_set_b = find(b,sb);
if(disjoint_set_a == disjoint_set_b)
{
if((sa+sb)%2==0)
{
flag = false;
continue;
}
}else
{
disjoint_set[disjoint_set_a] = disjoint_set_b;
}
}
if(flag) printf("BICOLORABLE.n");
else printf("NOT BICOLORABLE.n");
}
return 0;
}

染色法

//
Bicoloring
//
二分图 -- 染色法
#include <iostream>
#include <vector>
#include <cstring>
using std::ios;
using std::cin;
using std::cout;
using std::vector;
const int MAXSIZE = 210;
vector<int> G[MAXSIZE];
int color[MAXSIZE];
bool dfs(int u)
{
int len = G[u].size();
for(int i=0;i<len;i++)
{
int v = G[u][i];
if(color[v] == color[u]) return false;
if(!color[v])
{
color[v] = 3 - color[u];
if(!dfs(v)) return false;
}
}
return true;
}
int main()
{
int n,l,a,b;
while(scanf("%d",&n)!=EOF && n!=0)
{
memset(color,0,sizeof(color));
memset(G,0,sizeof(G));
scanf("%d",&l);
for(int i=0;i<l;i++)
{
scanf("%d%d",&a,&b);
G[a].emplace_back(b);
G[b].emplace_back(a);
}
color[0] = 1;
if(dfs(0)) printf("BICOLORABLE.n");
else printf("NOT BICOLORABLE.n");
}
return 0;
}

最后

以上就是自然服饰为你收集整理的Bicoloring (并查集/二分图)　（并查集方法有缺陷）题意思路的全部内容，希望文章能够帮你解决Bicoloring (并查集/二分图)　（并查集方法有缺陷）题意思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。