关于通过colors数组信息划分二分图的Bug
来源：4-11 实现二分图检测
软件工程小白菜
2019-08-15
波波老师您好，如果我们按照colors[v] = 0还是1进行二分图的分组，就会有一个小bug。就是如果这张图中有多个联通分量时，这样划分是不对的，比如说我们之前的g：
7 6
0 1
0 2
1 3
1 4
2 3
2 6
我们知道这张图有两个联通分量：5和剩下的所有。但是如果我们只是简单的把colors[v] = 0的所有顶点分为一组，我们会错误的把 [0, 3, 4, 5, 6]分为一组，[1, 2]分为另外一组。因为我们都知道，5和其余的点不在一个联通分量上。
写回答
1回答
-
虽然 5 不在任何联通分量上，但是把 5 划分给 0 3 4 6 是没有问题的。因为，这个划分，依然满足二分图的定义，即：
1）将二分图的所有顶点分成了两部分：[0, 3, 4, 5, 6] 和 [1, 2]
2）所有的边，都肯定一个端点取自一部分，另一个端点取自另一部分
实际上，对于这个图，将 5 划分给 [1,2]，也是ok的，即 [0, 3, 4, 6] 和 [1, 2, 5]，同样满足定义。
所以，对于非联通图，二分图的划分不是唯一。但只要满足定义，它就是一个二分图。对于非联通图，只要每个连通分量是一个二分图，整体就一定是一个二分图：）
极端情况，对于一个图，有 V 个顶点， 0 条边。这个图是一个二分图。顶点怎们划分都满足二分图的定义。
继续加油！：）
522019-08-15
相似问题