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:trueExplanation: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:falseExplanation: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]`

.

class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: color = collections.defaultdict(lambda: -1) def dfs(v, cur_color): if color[v] != -1: return color[v] == cur_color color[v] = cur_color return all(dfs(e, cur_color ^ 1) for e in graph[v]) return all(dfs(v, 0) for v in range(len(graph)) if color[v] == -1)