01 二分图

​ 二分图算法也称为染色法，是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么图为二分。

​ 二分图定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

785 判断二分图 (opens new window)

给定一个图，判断其是否可以二分

输入是邻接链表表示的图（如位置 0 的邻接链表为 [1,3]，表示 0 与 1、0 与 3 相连）；输出是一个布尔值，表示图是否二分。

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

解析：

​ 利用队列和广度优先搜索，我们可以对未染色的节点进行染色，并且检查是否有颜色相同的相邻节点存在。如果遍历完所有节点没有颜色相同的相邻节点，则该图为二分图；否则就不是二分图。在遍历过程中，我们用 0 表示未检查的节点，用 1 和 2 表示两种不同的颜色。

​ 我们任选一个节点开始，将其染成 1 色，并从该节点开始对整个无向图进行遍历；

​ 在遍历的过程中，如果我们通过节点 u 遍历到了节点 v，那么会有两种情况：如果 v 未被染色，那么我们将其染成与 u 不同的颜色，并对 v 直接相连的节点进行遍历；如果 v 已经被染色，并且颜色与 u 相同，那么说明给定的无向图不是二分图，可以直接退出并返回 False。

​ 当遍历完成时，说明给定的无向图是二分图，返回 True。

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        if(graph.empty()){
            return false;
        }
        vector<int> color(graph.size(),0);
        queue<int> q;
        for(int i=0;i<graph.size();++i){
            if(!color[i]){
                q.push(i);
                color[i] = 1;
            }
            while(!q.empty()){
                int node = q.front();
                q.pop();
                // 对 v 直接相连的节点进行遍历
                for(const auto& j: graph[node]){
                    if(!color[j]){
                        q.push(j);
                        color[j] = color[node] == 2?1:2;
                    }else if(color[j] == color[node]){
                        return false;
                    }
                }
            }
        }
        return true;
    }
};