Description

Submission

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);
        queue<int> q;
        
        for(int i = 0; i < n; ++i) {
            q.push(i);
            if(color[i] != -1) continue; // bicolor: 0 or 1, -1 for not visited yet
            color[i] = 1;

            while(!q.empty()) {
                auto cur = q.front();
                q.pop();

                for(auto x: graph[cur]) {
                    if(color[x] == -1) {
                        color[x] = 1 - color[cur];
                        q.push(x);
                    } else if(color[x] == color[cur]) return false;
                }
            }
        }

        return true;
    }
};

References