785. 判断二分图

785. 判断二分图

染色法

class Solution {
public:

    vector<vector<int>> graph;
    vector<int> color;

    bool dfs(int u, int c) {
        if (color[u] && color[u] != c)return false;
        for (auto i:graph[u]) {
            if (color[i]) {
                if (color[i] == c)return false;
            } else {
                color[i] = 3 - c;
                if (!dfs(i, 3 - c))return false;
            }
        }
        return true;
    }

    bool isBipartite(vector<vector<int>> &_graph) {
        graph = _graph;
        int n = graph.size();
        color.resize(n);

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

        return true;
    }
};