算法

(DFS) $O(n+m)$

二分图染色模板题

通过黑白染色我们可以判断一个无向图是否是二分图：
遍历整个图, 将相邻的节点染成不同的颜色, 如果可以完成这个遍历(即染色过程没有冲突), 说明是二分图。
可以用BFS或DFS来实现, 只需要根据当前节点的颜色设定下一个节点的颜色即可， 如果下一个节点已经被染成了相同的颜色, 说明发生了冲突。

C++ 代码

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);
        for (int i = 0; i < n; i++) {
            if (!color[i] && !colored(i, graph, color, 1)) {
                return false;
            }
        }
        return true;
    }

private:
    bool colored(int now, vector<vector<int>> &graph, vector<int> &color, int c) {
        color[now] = c;
        for (int nxt : graph[now]) {
            if (!color[nxt] && !colored(nxt, graph, color, -c)) {
                return false;
            }
            else if (color[nxt] == c) {
                return false;
            }
        }
        return true;
    }
};