为什么我们不能通过简单的迭代来确定图是否是二分图？

Question

这就是我要解决的问题

我们想要将一组 n 人（标记为 1 到 n）分成任意大小的两组。每个人都可能不喜欢某些人，他们不应该加入同一群体。给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi] 表示标记为 ai 的人不喜欢标记为 bi 的人，如果可以通过这种方式将每个人分成两组，则返回 true。

这可以通过 Python 中的 BFS 相当简单地解决：

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = defaultdict(set)
    for a, b in dislikes:
        graph[a-1].add(b-1)
        graph[b-1].add(a-1)

    q = deque({0})
    colors = [None]*n
    for i in range(n):
        if colors[i] is None:
            q = deque({i})
            colors[i] = 0
            while q:
                cur = q.popleft()
                for d in graph[cur]:
                    if colors[d] is None:
                        q.append(d)
                        colors[d] = 1 - colors[cur]
                    elif colors[d] == colors[cur]:
                        return False
    return True

但是，当我尝试通过简单迭代在线性时间内完成此操作时，算法失败

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = defaultdict(set)
    for a, b in dislikes:
        graph[a].add(b)
        graph[b].add(a)

    colors = {
        0: set(),
        1: set()
    }
    for i in range(n):
        if i in colors[0]:
            colors[1].update(graph[i])
        elif i in colors[1]:
            colors[0].update(graph[i])
        else:
            colors[0].add(i)
            colors[1].update(graph[i])

    return not (colors[0] & colors[1])

为什么第二种算法不起作用，有没有办法在没有某种类型的 BFS/DFS/Union Find 的情况下解决这个问题？我不明白为什么“递归”算法是必要的。为什么我们需要重新检查旧节点而不仅仅是比较集合？

Answer 1

假设这是你的图表：

0 - 3 - 2 - 1

您首先访问节点 0，然后访问节点 1。您的算法将节点 0 和 1 绘制为相同的颜色，但这些节点需要使用相反的颜色。

您的算法假设，如果它尚不知道节点需要什么颜色，则该节点可以是任何颜色。但这种假设是错误的。与广度优先搜索不同，广度优先搜索强制连接到它访问的节点的所有节点的颜色，您的代码仅强制节点的直接邻居的颜色，这不足以避免颜色分配冲突。