## Description

https://leetcode.com/problems/design-add-and-search-words-data-structure/

There is an **undirected** graph with `n`

nodes, where each node is numbered between `0`

and `n - 1`

. You are given a 2D array `graph`

, where `graph[u]`

is an array of nodes that node `u`

is adjacent to. More formally, for each `v`

in `graph[u]`

, there is an undirected edge between node `u`

and node `v`

. The graph has the following properties:

- There are no self-edges (
`graph[u]`

does not contain`u`

). - There are no parallel edges (
`graph[u]`

does not contain duplicate values). - If
`v`

is in`graph[u]`

, then`u`

is in`graph[v]`

(the graph is undirected). - The graph may not be connected, meaning there may be two nodes
`u`

and`v`

such that there is no path between them.

A graph is **bipartite** if the nodes can be partitioned into two independent sets `A`

and `B`

such that **every** edge in the graph connects a node in set `A`

and a node in set `B`

.

Return `true`

* if and only if it is bipartite*.

**Example 1:**

Input:graph = [[1,2,3],[0,2],[0,1,3],[0,2]]Output:falseExplanation:There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

**Example 2:**

Input:graph = [[1,3],[0,2],[1,3],[0,2]]Output:trueExplanation:We can partition the nodes into two sets: {0, 2} and {1, 3}.

**Constraints:**

`graph.length == n`

`1 <= n <= 100`

`0 <= graph[u].length < n`

`0 <= graph[u][i] <= n - 1`

`graph[u]`

does not contain`u`

.- All the values of
`graph[u]`

are**unique**. - If
`graph[u]`

contains`v`

, then`graph[v]`

contains`u`

.

## Explanation

We can use the coloring approach with either breadth-first search or depth-first search, to see if nodes can be divided into half.

## Python Solution

```
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
visited = set()
colors = {}
for i in range(len(graph)):
if i in visited:
continue
queue = []
queue.append(i)
colors[i] = 0
visited.add(i)
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor not in colors:
colors[neighbor] = 1 if colors[node] == 0 else 0
queue.append(neighbor)
visited.add(neighbor)
else:
if colors[neighbor] == colors[node]:
return False
return True
```

- Time Complexity: O(N).
- Space Complexity: O(N).