判断二分图

难度: Medium

存在一个 无向图 ，图中有 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：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：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

Submission

运行时间: 26 ms

内存: 16.8 MB

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        colors = [0] * n
        def dfs(i, color):
            colors[i] = color
            for neibor in graph[i]:
                if colors[neibor] == color: return False
                if colors[neibor] == 0 and not dfs(neibor,-1*color): return False
            return True
        for i in range(n):
            if colors[i] == 0 and not dfs(i,1): return False
        return True

Explain

这个题解使用了深度优先搜索（DFS）的方法来判断图是否为二分图。基本思路是：对图进行遍历，将相邻的节点着不同的颜色（用1和-1表示）。如果在遍历的过程中，发现某个节点的所有相邻节点都已经着色，并且有相同颜色的相邻节点，则说明不是二分图，返回False。如果遍历完整个图，都没有发现相邻节点有相同颜色的情况，则说明是二分图，返回True。

时间复杂度: O(节点数+边数)

空间复杂度: O(节点数)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        colors = [0] * n  # 用colors数组记录每个节点的颜色，初始为0表示未着色
        
        def dfs(i, color):
            colors[i] = color  # 给当前节点i着色
            for neibor in graph[i]:  # 遍历节点i的所有相邻节点
                if colors[neibor] == color: return False  # 如果相邻节点颜色相同，则不是二分图
                if colors[neibor] == 0 and not dfs(neibor,-1*color): return False  # 如果相邻节点未着色，则递归调用DFS为其着色
            return True
        
        for i in range(n):  # 遍历所有节点
            if colors[i] == 0 and not dfs(i,1): return False  # 如果当前节点未着色，则调用DFS为其着色，如果着色失败，则不是二分图
        return True  # 遍历完所有节点，都没有出现矛盾，说明是二分图

Explore

题解中通过在主函数内部使用一个循环，对每个节点进行检查，从而处理不连通的情况。如果一个节点尚未着色（即`colors[i] == 0`），那么就从这个节点开始执行DFS。这保证了即使图是不连通的，每个连通子图都会被遍历到。每个连通子图的着色开始于一个任意节点，DFS负责检查此子图是否为二分图。如果所有连通子图都是二分的，则整个图是二分图。

在此题解中，使用1和-1作为颜色标志是为了简化颜色切换和比较的逻辑。通过使用1和-1，可以非常方便地通过乘以-1来切换当前的颜色，即从1变为-1，或从-1变为1。这种方式比使用其他数字或颜色标识如0和1更简洁，因为0和1需要额外的逻辑来切换颜色（比如使用条件语句）。使用1和-1可以直接利用数学运算来简化代码。

在DFS函数中，如果遇到一个已经着色的节点，会检查这个节点的颜色是否与当前尝试着色的颜色相同。如果颜色相同，意味着在同一个连通子图中存在相同颜色的相邻节点，这违反了二分图的定义，所以会返回False。如果颜色不同，则继续DFS过程，因为这表明当前的着色是有效的。这种方式确保任何时候遇到已着色的节点都能正确处理颜色冲突。

是的，题解中的DFS确保每个节点最多被访问一次，这意味着算法的时间复杂度与图中的节点数和边数总和线性相关（O(V + E)，其中V是节点数，E是边数）。因此，无论是稀疏图还是密集图，只要图的规模（节点和边的数量）在可接受的计算能力范围内，算法都能有效地处理。这使得算法适用于大型图结构，包括稀疏和密集图。