leetcode：785. 判断二分图

题目

存在一个 无向图 ，图中有 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：
[中等] 785. 判断二分图 - 图1

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

示例 2：
[中等] 785. 判断二分图 - 图2

  1. 输入：graph = [[1,3],[0,2],[1,3],[0,2]]
  2. 输出：true
  3. 解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

解答 & 代码

染色法：类似于岛屿问题，DFS 处理每个连通子图，进行染色，使得相邻结点的颜色不同。如果能顺利对所有节点染色，则说明是二分图；否则如果某个节点的颜色存在冲突，则不是二分图

  1. class Solution {
  2. private:
  3.     static constexpr int UNCOLORED = 0;        // 未着色
  4.     static constexpr int RED = 1;            // 红色
  5.     static constexpr int BLUE = 2;            // 蓝色
  6.     vector<int> colorList;                    // 记录每个节点颜色的数组
  7.     bool result;                            // 结果（是否为二分图）
  9.     // DFS 遍历，遍历的同时给节点染色，使得相邻结点的颜色不同
  10.     void dfs(vector<vector<int>>& graph, int idx, int color)
  11.     {   
  12.         colorList[idx] = color;                            // 给当前节点染色
  13.         int neighborColor = color == RED ? BLUE : RED;    // 相邻节点的颜色
  14.         // 遍历每个相邻节点
  15.         for(int j = 0; j < graph[idx].size(); ++j)
  16.         {
  17.             int neighbor = graph[idx][j];                // 相邻节点编号
  18.             // 如果该相邻节点未着色，说明为被访问过，染色并继续 DFS
  19.             if(colorList[neighbor] == UNCOLORED)
  20.             {
  21.                 dfs(graph, neighbor, neighborColor);
  22.                 if(result == false)
  23.                     return;
  24.             }
  25.             // 否则如果相邻节点也被着色，且和当前节点颜色一样，则将结果置为 false，停止遍历
  26.             // 说明不是二分图
  27.             else if(colorList[neighbor] != neighborColor)
  28.             {
  29.                 result = false;
  30.                 return;
  31.             }
  32.         }
  33.     }
  34. public:
  35.     bool isBipartite(vector<vector<int>>& graph) {
  36.         int len = graph.size();
  37.         colorList.resize(len, UNCOLORED);
  38.         result = true;
  39.         // 不一定是连通图，因此需要对每个连通子图都进行一次 DFS 染色
  40.         for(int i = 0; i < len && result; ++i)
  41.         {
  42.             // 如果当前节点未被着色，说明属于新的连通子图，对该连通子图 DFS 遍历并染色
  43.             if(colorList[i] == UNCOLORED)
  44.                 dfs(graph, i, RED);
  45.         }
  46.         return result;
  47.     }
  48. };

复杂度分析：设图的点数 n，边数 m

  • 时间复杂度 O(n + m)：
  • 空间复杂度 O(n)：
    • colorList 数组长为 n
    • 栈深度最大为 n

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 80.73% 的用户
  4. 内存消耗：13.1 MB, 在所有 C++ 提交中击败了 77.68% 的用户