题目描述

给定一个无向图 graph，当这个图为二分图时返回 true。

如果我们能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，我们就将这个图称为二分图。

graph 将会以如下方式给出：graph[i] 表示图中与结点 i 相连的所有结点的 j。每个节点都是一个在 0 到 graph.length - 1 之间的整数。这图中没有自环和平行边：graph[i] 中不存在 i，并且 graph[i] 中没有重复的值。

样例

输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

提示

• graph 的长度范围为 [1, 100]。
• graph[i] 中的元素的范围为 [0, graph.length - 1]。
• graph[i] 不会包含 i 或者有重复的值。
• 图是无向的：如果 j 在 graph[i] 里边, 那么 i 也会在 graph[j] 里边。

算法

(宽度优先遍历 / BFS) $O(n + m)$

1. 一个图是二分图当且仅当这个图不存在奇数环，也就是这个图可以被黑白两种颜色染色：染色的规则是相邻两个点之间不能染相同的颜色。
2. 我们通过宽度优先遍历，来对这个图进行染色。首先结点的颜色都是未染色状态，即 -1。我们随便找一个 -1 的点开始染色，不妨初始染 0。然后其余相邻的 -1 的结点就染 1。如果相邻的结点中有相同颜色的，则发现了奇数环，可以直接宣布不是二分图。
3. 将所有结点都染色后，没有冲突，则说明这个图是二分图。

时间复杂度

• 每个结点和每条边仅遍历一次，故时间复杂度为 $O(n + m)$。$n$ 是点数，$m$ 是边数。

空间复杂度

• 需要额外的数组存储结点颜色，需要队列进行遍历，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    bool bfs(int S, vector<int>& color, const vector<vector<int>>& graph) {
        color[S] = 0;
        queue<int> q;
        q.push(S);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &v : graph[u]) {
                if (color[v] == color[u])
                    return false;

                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                }
            }
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);

        for (int i = 0; i < n; i++)
            if (color[i] == -1) {
                if (!bfs(i, color, graph))
                    return false;
            }

        return true;
    }
};