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

Question

这就是我要解决的问题

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

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

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

说这是你的图表：

A - B - C - D

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