Given an undirected graph G, return true if and only if it is bipartite.

Problem Note

  • A graph is bipartite if we can split it's set of nodes into two independent subsets G1 and G2 such that every edge in the graph has one node in G1 and another node in G2.
  • The graph is given in the following form: G[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 G.length - 1.
  • There are no self edges or parallel edges: G[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.