关于通过colors数组信息划分二分图的Bug

Question

波波老师您好，如果我们按照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和其余的点不在一个联通分量上。

Answer 1

liuyubobobo 2019-08-15 01:37:13

虽然 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 条边。这个图是一个二分图。顶点怎们划分都满足二分图的定义。

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！老师是想说将5划分给[1,2]吗

• liuyubobobo 回复 提问者 软件工程小白菜 #2

  对，之前笔误，已经修正了：）