检查图是否为二分图并在添加每个新边时执行

Question

给定一个图的多个边输入，例如（第一行是连接数量）：

4
1 2
2 3
5 6
1 5

我需要在每次输入之后检查图是否仍然是二分图，如果不是，我们将中断程序。 我认为这是一个图着色问题，但我无法实现它，请提供一些算法来帮助我。

- user8378799

---

图着色是正确的。尝试找到一种双色着色，这非常简单（除了第一个节点外每个节点只有一种选择）。如果存在这样的着色，则它是二分图。 - tobias_k

你能否详细说明一下？我还没有做过任何图着色问题，只是在寻找这个问题的答案时了解到它。 - user8378799

你有时间限制吗？ - dWinder

@DavidWinder 实际上这是 https://www.codechef.com/JULY18A/problems/GEARS 问题的一个子部分。 - user8378799

Answer 1

如果您可以找到图的二部分，那么该图就是二分的。实现起来非常简单，因为没有回溯；对于每个连续的节点，只有一种颜色可用，如果那种颜色不可用，因为其中一个邻居已经有了那种颜色，则该图不是二分的。

例如，您可以将其实现为深度优先搜索，每次为具有颜色A和颜色B的节点分别跟踪两个集合。每次扩展新节点时，都会切换颜色，如果该节点应被着色为A，但已在B集中，则该图不是二分的。

尽管如此，您的情况似乎有些不同，在添加每个单独的边后检查图是否为二分的。您仍然可以在每次迭代中在整个图上运行DFS，但这可能太慢了。

相反，为每个（仍然）未连接的子图跟踪具有颜色A和颜色B的节点的两个集合。因此，当您添加边(x, y)时：

- 检查x和y所属的子图（使用某种映射/字典） - 如果两者都不属于子图，请启动新的子图 - 如果一个属于子图，而另一个尚未在图中，请将另一个节点赋予已包含节点的相反颜色 - 如果两者属于不同的子图，请将子图合并为一个（合并颜色集）; 这可能需要翻转其中一个图的颜色，以便x和y不会以相同的颜色结束; 确保更新映射，使所有这些节点指向合并的图 - 如果两个都属于同一个子图，则它们必须在不同的颜色集中，否则该图不是二分的。

在您的情况下，每个边后的子图映射可能如下所示：

1 2 -> {1: ({1}, {2}), 2: (see 1)}
2 3 -> {1: ({1, 3}, {2}), 2: (see 1), 3: (see 1)}
5 6 -> {1: ({1, 3}, {2}), 2: (see 1), 3: (see 1), 5: ({5}, {6}), 6: (see 5)}
1 5 -> {1: ({1, 3, 6}, {2, 5}), 2: (see 1), 3: (see 1), 5: (see 1), 6: (see 1)}

- tobias_k

---

非常感谢，这很有帮助。 - user8378799