785.cpp

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, -1);
        for(int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!BFS(graph, colors, 0, i)) {
                    return false;
                }
            }
        }
        return true;
    }
    bool BFS(vector<vector<int>>& graph, vector<int>& colors, int color, int node) {
        queue<int> q;
        q.push(node);
        colors[node] = color;
        while(!q.empty()) {
            int i = q.front(), c = colors[i];
            q.pop();
            for(auto next : graph[i]) {
                if (colors[next] == -1) {
                    q.push(next);
                    colors[next] = 1 - c;
                } else {
                    if (colors[next] != (1 - c)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};