# 785. Is Graph Bipartite? (Medium)
假如没有被染色过，则染色并入队。
邻接表天生适合 bfs，不适合 dfs
不行，由于是无向图，dfs 能做吗？应该也行，另外开辟数组记录是否遍历过该结点。
在这里是间隔性染色的。
class Solution { | |
public: | |
bool isBipartite(vector<vector<int>>& graph) { | |
int n = graph.size(); | |
vector<int> colors(n, 0); | |
queue<int> q; | |
for(int i = 0; i < n; i++) { | |
if(colors[i] == 0) { | |
colors[i] = 1; | |
q.push(i); | |
} | |
while (!q.empty()) { | |
int node = q.front(); | |
q.pop(); | |
for(const int &j : graph[node]) { | |
if(colors[j] == 0) { | |
q.push(j); | |
colors[j] = colors[node] == 1? 2: 1; | |
}else if(colors[j] == colors[node]) { | |
return false; | |
} | |
} | |
} | |
} | |
return true; | |
} | |
}; |
