class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        if(n==0)
            return true;
        queue<int> q;
        vector<int> color(n, 0);
        // 0表示未染色，1表示一种颜色，2表示一种颜色
        // 如果是非连通图，for循环会执行多次，如果是连通图，for循环只会执行一次
        for(int i = 0; i < n; i++){
           // cout<<"i:"<<i<<endl;
            if(color[i]==0){   // 如果未染色，先随机染一种颜色
                q.push(i);
                color[i] = 1;
            }
            while(!q.empty()){
                int node = q.front();
                q.pop();
                for(auto j:graph[node]){ //遍历与node相连的节点，注意队列中的节点肯定是染过色的
                    if(color[j]==0){ // 如果node相连的节点未染色
                        q.push(j);   //先加入队列中，然后进行染色，但是染色颜色不应该与node相同
                        if(color[node] == 1)
                            color[j] = 2;
                        else
                            color[j] = 1;
                    }else if(color[j]==color[node]){  // 如果node相连节点染色与node相同
                        return false;
                    }

                }
            }
        }
        return true;
    }
};