a graph is bipartite if we can split it's set of nodes into two independent subsets A and B (that means the two subsets are disjoint and the union of the two subsets can form the original set) such that every edge in the graph has one node in A and another node in B.
785. Is Graph Bipartite?
886. Possible Bipartition

• 注意使用 I'm gonna be using 的句式
  I'm gonna be using an int array called color to keep tracking of the color of each node, with this array we can also know if the node has been visited or not which is a part of standard BFS
  if we can dye all nodes such that every two adjacent nodes have different color, this is a bipartite graph.

785. Is Graph Bipartite?

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        Queue<Integer> que = new LinkedList<>();
        int[] color = new int[n];
        //we have a for loop in the puter part because there may be more than one connected component
        for (int i = 0; i < n; i++) {
            //if the color of node-i is 0, it means node-i has not been visited before
            //we dye this node with color-1, and add it into queue
            if (color[i] == 0) {
                que.offer(i);
                color[i] = 1;
            }
            //then we can do a regular BFS
            //every BFS can dye all nodes in the same connected component
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int next : graph[cur]) {
                    //if next node has not been visited, we dye it with the opposite color with cur node
                    //and don't forget to add it into queue
                    if (color[next] == 0) {
                        que.offer(next);
                        color[next] = color[cur] == 1 ? 2 : 1;
                    }
                    //if the next node has been visited, we just check its color 
                    //if the color of next node is the same with the color of the current node
                    //we can say this is not a bipartite graph, just return false
                    //else their colors are different, this is allowed, we just continue
                    else {
                        if (color[cur] == color[next]) return false;
                        else continue;
                    }
                }
            }
        }
        return true;
    }
}

886. Possible Bipartition

class Solution {
    //this is a graph problem, if the graph is bipartite
    //we can split people into two groups, return true
    public boolean possibleBipartition(int N, int[][] dislikes) {
        //build a graph with adjacent list
        List<Integer>[] g = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] d : dislikes) {
            g[d[0]].add(d[1]);
            g[d[1]].add(d[0]);
        }
        
        int[] color = new int[N+1];
        Queue<Integer> que = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            //unvisited, there may be more than one connected components
            if (color[i] == 0) {   
                que.offer(i);
                color[i] = 1;
            }
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int next : g[cur]) {
                    if (color[next] == 0) {
                        que.offer(next);
                        color[next] = color[cur] == 1 ? 2 : 1;
                    } else {
                        if (color[next] == color[cur]) return false;
                        else continue;
                    }
                }
            }
        }
        return true;
    }
}