CONY的世界

785. Is Graph Bipartite?

Given a graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent ubsets.

Note:

• graph will have length in range [1, 100].
• graph[i] will contain integers in range [0, graph.length - 1].
• graph[i] will not contain i or duplicate values.

這題首先要了解的是Bipartite 的意思，every edge in the graph has one node in A and another node in B.

也就是說可以考慮從一個node開始先著成紅色，然後鄰居都著成藍色，然後依此類推（邊著邊判斷有沒有conflict)

不過要注意的是graph 上所有點不一定都有edge connected，因為bipartites 只是要各edge 兩端可以各對應到一個set就好，所以是有可能node的edge 是[ ] 的情形 

或是graph 是forest 的情形

因此為了避免沒走到的點或是forest，在最外層要加的 for loop 跑過所有的 vertex ，確保每個點都有走到 （類似DFS 的做法）

參考資料geeks for geeks https://www.geeksforgeeks.org/bipartite-graph/

class Solution {
    public boolean Bipartite(int[][] graph, HashSet<Integer> cur, HashSet<Integer> compare, int index) {
        Deque<Integer> que = new ArrayDeque();
        que.addLast(index); 
        cur.add(index);
        int size=que.size();
        while(!que.isEmpty()){
            int node = que.removeFirst();
            for(int neighbor:graph[node]){
                if(cur.contains(neighbor))
                   return false;
                if(!compare.contains(neighbor)){
                    compare.add(neighbor);
                    que.addLast(neighbor);
                }
            }
            if(--size == 0) {
                HashSet<Integer> temp = cur;
                cur=compare;
                compare = temp;
                size = que.size();
            }
        }
        return true;
    }
    public boolean isBipartite(int[][] graph) {
        HashSet<Integer> cur = new HashSet();
        HashSet<Integer> compare = new HashSet();
        for(int index=0; index<graph.length; index++) {
            if(!cur.contains(index) && !compare.contains(index)) {
                if(Bipartite(graph, cur, compare, index) == false)
                    return false;
            }
        }
        return true;
    }
}