A bipartite graph is a special kind of graph that consists of two vertex sets.

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.

class BipartiteChecker: def Bipartite(self, graph) -> bool: glen = len(graph) s = [] vis = [0] * glen for i in range(glen): if vis[i]: continue vis[i] = 1 s.append(i) while len(s): curr = s.pop() edges = graph[curr] for next in edges: if not vis[next]: vis[next] = vis[curr] ^ 3 s.append(next) elif vis[curr] == vis[next]: return False return True # Driver G = BipartiteChecker() ''' Matrx = [[1,2,3],[0,2],[0,1,3],[0,2]] ''' Matrx=[] while True: arr=list(map(str,input().split(" "))) if arr != ['']: Matrx.append(list(map(int,arr))) else: break print("True") if G.Bipartite(Matrx) else print("False")

**INPUT_1:**

1 2 3

0 2

0 1 3

0 2

**OUTPUT:**

False

**INPUT_2:**

1 3

0 2

1 3

0 2

**OUTPUT:**

True

**ILLUSTRATION**