785. 判断二分图

判定思路

说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色， 且相邻节点的颜色都不相同。

那么就可以用一个bool类型的visted数组进行存储

核心框架

// 图遍历框架
vector<bool> isBi;
vector<bool> color;  //false和true分别代表两种颜色
vector<bool> visited;
void traverse(Graph graph, int v) {
    //判定了不是就直接退出
    if(!isBi)return;

    // 防止走回头路进入死循环
    if (visited[v]) return;

    // 前序遍历位置，标记节点 v 已访问
    visited[v] = true;
    for (Vertex neighbor : graph.neighbors(v))
        traverse(graph, neighbor);
}