785. Is Graph Bipartite?

着色法 O(V+E) time O(v) space

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

    bool dfs(const vector<vector<int>> &graph, int node, int color) {
        if (colors[node] != 0) return colors[node] == color;
        colors[node] = color;
        for (int neighbor : graph[node]) {
            if (!dfs(graph, neighbor, -color)) return false;
        }
        return true;
    }

    vector<char> colors;
};