785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected).
• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
  A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

原题等于问：每个节点与其相连接的节点是否可以颜色不同？
通过BFS搜索，将每一层通过开关flag分组。
创建一个visited数组，记录分组和遍历情况。
当节点被放入错误的分组时，返回false。

注意因为图里的各个节点可能不连接，因此需要遍历对所有节点进行BFS搜索，通过visited的情况进行剪枝。

class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<int[]> q = new LinkedList<>();
        int[] visited = new int[graph.length];
        
        for(int i = 0; i < graph.length; i++){
            boolean flag = false;
            if(graph[i].length == 0 || visited[i] != 0) continue;
            q.add(graph[i]);
            visited[i] = 1;
            int size = 1;
        
            while(!q.isEmpty()){
                for(int j = 0; j < size; j++){
                    int[] node = q.poll();
                    for(int next : node){
                        if(visited[next] == 0){
                            q.add(graph[next]);
                        }
                        if(flag){
                            if(visited[next] == 2) return false;
                            visited[next] = 1;
                        }
                        else{
                            if(visited[next] == 1) return false;
                            visited[next] = 2;
                        }
                    }
                }
                flag = !flag;
                size = q.size();
            }
        }
        return true;
    }
}