给定图中边的多个输入，例如（第一行是连接数）：
4
1 2
2 3
5 6
1 5
我必须检查在每个输入之后，图是否仍然是二分的，如果图是非二分的，我们就中断。
我认为这是一个图着色问题，但我无法实现它，请帮助我提供一些算法这样做。
最佳答案
这个图是二部的，只要你能找到图的双色。这很容易实现，因为不涉及回溯；对于每个后续节点，只有一种颜色可用，如果该颜色不可能，因为其中一个邻居已经具有该颜色，则图不是二分图。
例如，可以将其实现为深度优先搜索，分别跟踪颜色为a和颜色为b的节点的两组。每次展开新节点时，都会切换颜色，如果该节点应为A颜色，但已在B集中，则该图不是二分图。
不过，您的情况似乎有点不同，在添加每个单独的边之后检查图是否是二分图。您仍然可以在每次迭代中对整个图运行dfs，但这可能太慢。
相反，对于每个（仍然）断开连接的子图，使用颜色A和颜色B跟踪两组节点。因此，当添加边时：
检查(x, y)和x属于的子图（使用某种地图/字典）
如果两者都不属于子图，则启动新的子图
如果一个属于子图，但另一个还不在图中，则给另一个节点与已包含的节点相反的颜色
如果两个子图都属于不同的子图，则将子图合并为一个子图（合并颜色集）；这可能需要翻转其中一个图的颜色，以便y和x不会以相同的颜色结束；请确保更新映射，以便所有这些节点都指向合并的图
如果两者都属于同一个子图，则它们必须在不同的颜色集中，否则该图不是二部的。
在您的例子中，子图映射在每条边之后可能如下所示：
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)}