785. 判断二分图

Difficulty
Medium
Tags
BFS
URL
https://leetcode-cn.com/problems/is-graph-bipartite/
Star
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。
示例 1：
notion imagenotion image
输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
示例 2：
notion imagenotion image
输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。
提示：
  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不会包含 u
  • graph[u] 的所有值 互不相同
  • 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u
通过次数45,062提交次数86,925

法1 BFS

思路
染色法。
如果给的是一个完整的图，那么不需要for循环。
但是如果给的是不止一个图(即有些节点之间没有连接，使得图分为两个岛屿)，那么就需要单独判断每个小图。
BFS 默认染 -1 就可以，因为相邻的节点一定在一次同时染过了。
题解
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        self.colors = [-1] * len(graph)
        for i in range(0, len(graph)):
            # 遍历每一个没有染色的节点
            if self.colors[i] == -1:
                # 当前节点 的 邻域 没法成功染色
                if not self.bfs(graph=graph, i=i, color=0):
                    return False

        return True

    def bfs(self, graph, i, color):
        queue = []
        # 进队列的时候就对当前节点进行染色
        self.colors[i] = color
        queue.append(i)
        
        while queue:
            cur = queue.pop(0)
            for g in graph[cur]:
                # 染过色了
                if self.colors[g] != -1:
                    # 这个染的竟然和当前的是一样的？ 返回False
                    if self.colors[g] == self.colors[cur]:
                        return False
                # 还没染色，那就染呗，染成不一样的
                else:
                    self.colors[g] = 1-self.colors[cur]
                    queue.append(g)
        return True

法 2 DFS

思路
DFS不能默认染 -1
题解
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        self.colors = [0] * len(graph)
        for i in range(0, len(graph)):
            # 遍历每一个没有染色的节点
            if self.colors[i] == 0:
                # 当前节点 的 邻域 没法成功染色
                if not self.dfs(graph=graph, i=i, cur=1):
                    return False

        return True

    def dfs(self, graph, i, cur):
        # 将 i 染色为 cur 看行不行得通
        self.colors[i] = cur

        # 当前的已经被染色为 了 cur
        for neigh in graph[i]:
            if self.colors[neigh] == self.colors[i]:
                return False
            # 还没被染色？
            # 那就按照这个颜色去染，看看能不能染色成功
            elif self.colors[neigh] == 0:
                # 如果不行再return ,可以的话，应该去看之后的节点
                if not self.dfs(graph, neigh, cur*-1):
                    return False
            

        return True