人言落日是天涯
望极天涯不见家
唉，孤陋寡闻，第一次听到“染色”这个词。
简单来说，可以在深度遍历的过程中，依次将邻接点染成与自己相反的颜色。
在遍历的过程中，如果碰到已经被染色，但是和自己颜色一样的邻接点，就说明这个图无法被二分。
因为是深度遍历，同一个连通图在一次遍历中，都会被染色，所以每次深度遍历第一个结点的时候，任意颜色都可以的。
class Solution {
private:
bool dfs(vector<vector<int>>& graph, int v, int8_t c, vector<int8_t> &colors) {
if (colors[v] != 0) return true;
colors[v] = c;
for (int w : graph[v])
if (colors[w] == c || !dfs(graph, w, -c, colors)) return false;
return true;
}
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int8_t> colors(n);
for (int v = 0; v < n; v++) {
if (!dfs(graph, v, 1, colors))
return false;
}
return true;
}
};
