# 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](https://leetcode.com/shawntsai) at [here](https://leetcode.com/problems/is-graph-bipartite/discuss/115503/java-BFS)

**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)**.)

```java
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)**

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code.taozirui.com/lc/graph-search/bfsdfs/is-graph-bipartite.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.