Is Graph Bipartite

Q: 判断图是否为二分图的时间复杂度是多少？

对于 m 条边，广度优先或深度优先着色的运行时间为 O(n + m)：每个节点着色一次，每条边从两端各比较一次。邻接列表和颜色占用 O(n + m) 空间。并查集也能得到相同的答案，运行时间为 O(n + m α(n))。

中等图队列

+10

一个图有 n 个节点，标签为 0 到 n-1。edges 中的每一对 [a, b] 都表示节点 a 和节点 b 之间的一条无向边。这个图可能分成几个互不相连的部分，有些节点也可能没有任何边。

如果可以将图中的节点分成两组，使每条边都连接一组中的一个节点和另一组中的一个节点，那么这个图就是二分图。如果图是二分图，返回 true，否则返回 false。

函数

isBipartite(n: integer, edges: integer-2d-array) → boolean

ninteger: 节点的数量，编号从 0 到 n-1
edgesinteger-2d-array: 无向边，每条边都是一对 [a, b]
返回值boolean: 如果节点可以分成两组，并且每条边都连接这两组中的节点，则为真；否则为假。

约束条件

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b]，其中 0 ≤ a, b ≤ n-1 且 a ≠ b
没有一条边会重复出现，无论方向如何。

示例

输入: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
输出: true
解释: 将节点 0 和 2 放在一组，将节点 1 和 3 放在另一组。这四条边都连接这两组。

输入: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
输出: false
解释: 边 [0, 1] 可以正常拆分，节点 5 没有边，但节点 2、3 和 4 构成了一个三角形。只要有一个部分不满足条件，答案就是 false。

进阶

当图不是二分图时，你能返回一个奇数长度的环作为证明，并按顺序列出环上的节点吗？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

为一个节点选择一个组，就会迫使与它相连的部分中的其他节点也确定分组：邻居要放入另一个组。用交替使用两种颜色的广度优先搜索为每个部分着色；当且仅当没有边的两端颜色相同时，图才是二分图。图可能不连通，因此每个未着色的节点都会启动一次新的搜索。

尝试每一种拆分方式

结果正确，但无法在最大的测试中运行完毕

思路

尝试每一种划分。把每个节点所属的组看作一位，因此 n 位组成一个二进制数，从 0 数到 2^n-1，就能遍历每一种划分一次。对于每一种划分，检查每条边；如果存在一种划分能让每条边都跨越两个组，就返回 true。节点数量每增加一个，划分数量就会翻倍：20 个节点大约有一百万种划分。

算法

对于从 0 到 2^n-1 的每个数字，根据第 i 位将节点 i 放入对应的组中。
如果每条边都连接两个不同的组，返回 true。
如果没有可行的划分，返回 false。

def isBipartite(n, edges):
    side = [0] * n  # side[x] is 0 or 1: the group of node x in the current split
    while True:
        # Does every edge cross between the two groups?
        if all(side[u] != side[v] for u, v in edges):
            return True
        # Move to the next split, counting in binary over side.
        i = 0
        while i < n and side[i] == 1:
            side[i] = 0
            i += 1
        if i == n:
            return False  # all 2^n splits have been tried
        side[i] = 1

对每个节点的邻居使用并查集

思路

无论一个节点被分到哪个组，它的所有邻居都会被分到另一个组，因此这些邻居属于同一组。对于每个节点，把它的所有邻居合并到一个并查集集合中；这样，一个集合就包含了必须位于同一侧的节点。如果一条边的两个端点属于同一个集合，那么它们就被迫留在同一个组中，因此这个图不是二分图。

这种检查能发现所有不符合条件的情况。在奇数环中，每次合并两条边，都会把环上的第一个节点和最后一个节点连在一起；而闭合边又会把这两个节点连起来。如果没有奇数环，那么每次合并的两个节点之间的距离都是偶数，因此它们位于同一侧。一个节点的第一个邻居，也就是它的锚点，可以代表它所有邻居所在的集合，因此你可以随着边依次经过来进行合并，而不需要邻接表。使用按大小合并和路径减半后，2m 次合并和 m 次检查的开销为 O(m α(n))。

算法

为每个节点设置 parent[x] = x 和 anchor[x] = -1。
对于每条边 [u, v]，如果任一端还没有锚点，就将另一端设为它的锚点。
将 v 合并到 anchor[u] 所属的集合中，并将 u 合并到 anchor[v] 所属的集合中。
如果某条边的两端属于同一个集合，则返回 false，否则返回 true。

def isBipartite(n, edges):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n
    anchor = [-1] * n  # the first neighbour seen for each node

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # All neighbours of a node must sit on one side: the side opposite the node.
    for u, v in edges:
        if anchor[u] == -1:
            anchor[u] = v
        if anchor[v] == -1:
            anchor[v] = u
        union(anchor[u], v)  # v joins the other neighbours of u
        union(anchor[v], u)  # u joins the other neighbours of v
    # An edge whose two ends were forced onto one side cannot cross.
    for u, v in edges:
        if find(u) == find(v):
            return False
    return True

对每个部分进行广度优先双色着色

思路

颜色冲突就意味着无法拆分。一个部分中的第一个颜色可以自由选择，翻转它就会翻转整个部分中的颜色；其他所有颜色都由边决定。搜索会根据节点到起点的距离是偶数还是奇数来为节点着色，因此只有当一个部分中存在奇数长度的环时，两个相邻节点才会有相同的颜色，这种情况下就无法拆分。

一次搜索只能看到它所在的部分，因此要遍历所有节点，并从每个仍未着色的节点开始一次新的搜索。在第三个示例中，从节点 0 开始搜索，会为节点 0 和 1 着色。从节点 2 开始搜索，会将节点 2 着为颜色 0，将节点 3 和 4 着为颜色 1，随后发现 [3, 4] 两端的颜色都是 1：false。每个节点只会着色并入队一次，2m 个列表项也各比较一次：时间和空间复杂度均为 O(n + m)。

算法

为每条边的两个端点都建立邻接表，并将所有颜色设为 -1。
按顺序处理每个未着色的节点，将其颜色设为 0，并将它放入队列。
取出一个节点。将每个未着色的邻居设为相反的颜色，并将其放入队列；如果邻居的颜色相同，则返回 false。
所有部分都着色后，返回 true。

from collections import deque


def isBipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = [-1] * n  # -1: not colored yet, otherwise 0 or 1
    for start in range(n):
        if color[start] != -1:
            continue
        # A new component: its first node can take either color.
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == -1:
                    # A neighbour must take the other color.
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # this edge stays inside one group
    return True

易错点和边界情况

只从节点 0 开始搜索。第三个示例在节点 0 附近没问题，但在节点 2、3 和 4 之间会出错。
只把每条边添加到一个列表中。对于边 [1, 0] 和 [2, 0]，节点 0 会得到颜色 0，而且看不到任何邻居；接着节点 1 也会得到颜色 0，它与节点 0 之间的边看起来就像发生了冲突，尽管路径可以正常分开。
弹出节点时才为它着色。这样一个节点可能会进入队列两次，第二次访问会覆盖第一次的颜色。应该在推入节点时为它着色。
把二分图和无环图混为一谈。正方形有环，但它是二分图；只有奇数环才会破坏这种划分。

常见问题3

判断图是否为二分图的时间复杂度是多少？

对于 m 条边，广度优先或深度优先着色的运行时间为 O(n + m)：每个节点着色一次，每条边从两端各比较一次。邻接列表和颜色占用 O(n + m) 空间。并查集也能得到相同的答案，运行时间为 O(n + m α(n))。

为什么奇数环会使图不是二分图？

沿着这个环走一圈，两个组必须交替出现：第一个、第二个、第一个、第二个。边数为奇数的环经过奇数次切换后会回到起点，因此起点必须同时属于两个组。图是二分图，当且仅当它没有奇数长度的环。

检查图是否为二分图时，应该使用 BFS 还是 DFS？

两种方式都可以：着色规则相同，只是访问顺序不同。对于大型图，建议使用显式栈实现 DFS，因为递归版本可能会为每个节点深入一层调用。

def isBipartite(n, edges):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

n = 4
edges = [[0, 1], [1, 2], [2, 3], [3, 0]]

预期输出

true