leetcode785.判断二分图

class Solution {
public:
bool isBipartite(vector>& graph) {
int n = graph.size();
if(n==0)
return true;
queue q;
vector color(n, 0);
// 0表示未染色，1表示一种颜色，2表示一种颜色
// 如果是非连通图，for循环会执行多次，如果是连通图，for循环只会执行一次
for(int i = 0; i // cout<<"i:"< 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;
}
};