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.

class Solution {

    public boolean isBipartite(int[][] graph) {

        if(graph == null){

            return false;

        }

        int v = graph.length;

        //if we only have 2 vertices, then it's a Bipartite

        if(v <= 2){

            return true;

        }

        int[] colors = new int[v];

        for(int i = 0; i < v; i++){

            if(colors[i] == 0 && !valid(graph, i, 1, colors)){

                return false;

            }

        }

        return true;

    }

    private boolean valid (int[][] graph, int cur, int color, int[] colors){

        if(colors[cur] != 0){

            return colors[cur] == color;

        }

        colors[cur] = color;

        for(int i : graph[cur]){

            if(!valid(graph, i, color * -1, colors)){

                return false;

            }

        }

        return true;

    }

}