785_判断二分图

类型：图

判断二分图 💛 ⭐

https://leetcode-cn.com/problems/is-graph-bipartite/

❓ 给你一个邻接数组表示的无向图（不一定是连通图，即可能由几个互不连通的子图构成），判断其是否是一个二分图。

二分图的定义是，对于每一条边，其两端的结点不能划分在同一个集合，如果在此约束下，整个图中的所有结点可以划分在两个集合内。那么这个图就可以被称为二分图。

💡 涂色法 - DFS

这是一道典型的涂色题，所谓涂色，也就是一种分类的方法，涂上同一种颜色的结点，就被视为分类到同一个集合。

比如我们以 1/-1 来代表两种颜色，那么我们可以从图中任一结点，以任意颜色开始涂色。由于我们最终关系的只是分好类，因此先涂 1 色或 -1 色都没关系，毕竟颜色只是一个区分。

题目的要求是相邻（由一条边所连接的两端）结点不能同色。

我们使用 DFS 和 BFS 都是可以的。

在 DFS 中，我们要做的是在遍历过程中携带颜色信息，每遍历一个结点就要切换一次颜色。如果我们在涂色过程中发现冲突，则返回失败。

# 我的实现 1
# 1/-1 分别表示两种颜色，0 表示未涂色
class Solution:
    def dfs(self, grid, colors, i, color, N):
        colors[i] = color
        for j in range(N):
            if grid[i][j] == 1:
								# 同一条边的两端同色了，失败
                if colors[j] == color:
                    return False
								# 切换颜色，继续涂
                if colors[j] == 0 and not self.dfs(grid, colors, j, -1 * color, N):
                    return False
        return True

    def isBipartite(self, graph: List[List[int]]) -> bool:
        N = len(graph)
        grid = [[0] * N for _ in range(N)]
        colors = [0] * N
				# 把邻接表转换成邻接矩阵，这样处理更直观
        for i in range(N):
            for j in graph[i]:
                grid[i][j] = 1
        for i in range(N):
						# 如果没涂色，则涂色。如果涂色失败，则直接返回失败
            if colors[i] == 0 and not self.dfs(grid, colors, i, 1, N):
                return False
        return True

# 我的实现 2
# 1/-1 分别表示两种颜色，0 表示未涂色
class Solution:

    def __init__(self):
        self.colors = []

    def dfs(self, i, color, graph):
        if not 0 in self.colors:
            return True

        # 检查顶点 i 是否可涂为当前颜色，没法图的话，说明冲突了，返回失败
        if any(self.colors[k] == color for k in graph[i]):
            return False

        # 涂色
        self.colors[i] = color
        for k in graph[i]:
						# 切换颜色，继续往下涂
            if self.colors[k] == 0:
                if not self.dfs(k, color * -1, graph):
                    return False

        return True

    def isBipartite(self, graph: List[List[int]]) -> bool:
        self.colors = [0] * len(graph)

        for i in range(len(graph)):
						# 没涂的话开始涂
            if self.colors[i] == 0:
                if not self.dfs(i, 1, graph):
                    return False
        return True

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED] * n
        valid = True

        def dfs(node: int, c: int):
            nonlocal valid
            color[node] = c # 涂色
            cNei = (GREEN if c == RED else RED)
            for neighbor in graph[node]:
								# 旁边还没涂，切换颜色继续往下涂
                if color[neighbor] == UNCOLORED:
                    dfs(neighbor, cNei)
                    if not valid:
                        return
								# 旁边涂了，检查一下冲不冲突
                elif color[neighbor] != cNei:
                    valid = False
                    return

        for i in range(n):
						# 没涂的开始涂
            if color[i] == UNCOLORED:
                dfs(i, RED)
                if not valid:
                    break

        return valid

时间复杂度：O(n + m)，n 指结点数，m 指边数。空间复杂度：O(n)，n 指结点数

💡 涂色法 - BFS

按层涂也是一样的，每一层翻转一个颜色，如果发现冲突了，则返回失败。

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED] * n

        for i in range(n):
            if color[i] == UNCOLORED:
                q = collections.deque([i])
                color[i] = RED
                while q:
                    node = q.popleft()
                    cNei = (GREEN if color[node] == RED else RED)
                    for neighbor in graph[node]:
                        if color[neighbor] == UNCOLORED:
                            q.append(neighbor)
                            color[neighbor] = cNei
                        elif color[neighbor] != cNei:
                            return False

        return True

时间复杂度：O(n + m)，n 指结点数，m 指边数。空间复杂度：O(n)，n 指结点数