## 785. Is Graph Bipartite?

Given an undirected `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 subsets.
``````

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.
• The graph is undirected: if any element `j`is in `graph[i]`, then `i`will be in `graph[j]`.

Thoughts:

1. DFS: color each node:
1. for each node, first check if it has been colored, if is, return current color value == color to be added
2. color the node
3. try color all of its neightbor with different value, if failed, returned false; else return true
2. BFS: we need to check each if each cluster(edges linked together) is Bipartite. By shawntsai at here

Code: BFS T:(V+E); S: O(E): ( For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E (total number of edges). So, the complexity of DFS is O(V) + O(E) = O(V + E); for an undirected graph, each edge will appear twice. Once in the adjacency list of either end of the edge. So, the overall complexity will be O(V) + O (2E) ~ O(V + E).)

``````class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors, -1);

for (int i = 0; i < n; i++) {              //This graph might be a disconnected graph. So check each unvisited node.
if (colors[i] == -1 && !validColor(graph, colors, 0, i)) {
return false;
}
}
return true;
}

public boolean validColor(int[][] graph, int[] colors, int color, int node) {
if (colors[node] != -1) {
return colors[node] == color;
}
colors[node] = color;
for (int next : graph[node]) {
if (!validColor(graph, colors, 1 - color, next)) {
return false;
}
}
return true;
}
}
``````

Code: BFS T:(V+E); S:O(V)

``````class Solution {
public boolean isBipartite(int[][] graph) {
//BFS
// 0(not meet), 1(black), 2(white)
int[] colors = new int[graph.length];
for (int i = 0; i < graph.length; i++) {
if (graph[i].length != 0 && colors[i] == 0) {
colors[i] = 1;
// BFS
Queue<Integer> q = new LinkedList<>();
q.offer(i);
while(! q.isEmpty()) {
int cur = q.poll();
for (int v: graph[cur]) { // expand its neighbor
if (colors[v] == 0) {
colors[v] = (colors[cur] == 1) ? 2 : 1;
q.offer(v);
} else {
if (colors[v] == colors[cur]) return false;
}
}
}
}
}
return true;
}
}
``````