题目

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

题解

有点像简化版的地图着色问题。

每走一步，颜色翻转一下，并且染色。

当遇到已经染过色的节点时，

• 如果颜色正确，则停止此路径
• 如果颜色错误，则返回 false

DFS完成之后，返回 true。

另外，由于本题不保证是连通图，所以对于非连通图来说，可以将两个连通分量独立考察。

详见草稿：

class Solution {
    int N;

    public boolean isBipartite(int[][] graph) {
        N = graph.length;

        int[] color = new int[N];
        for (int i = 0; i < N; i++) { // 不保证是连通图
            if (color[i] == 0 && !dfs(graph, color, i, 1)) return false;
        }
        return true;
    }

    public boolean dfs(int[][] graph, int[] color, int i, int flag) {
        if (color[i] == 0) { // 未上色
            color[i] = flag;
            for (int j : graph[i]) {
                if (!dfs(graph, color, j, -flag)) return false;
            }
            return true;
        } else { // 已上色
            return color[i] == flag;
        }
    }
}