# Is Graph Bipartite?

Contributed by
Medium
0/80
+4 more

## Problem Statement

#### You are given an undirected graph consisting of βNβ nodes from 0 to βNβ - 1. You are given a list βEDGESβ of size βMβ, consisting of all the edges of this undirected graph. Determine whether the given graph is Bipartite or not.

##### Note:
``````The graph has no self-edges, no parallel edges.

The graph may not be connected.

A graph is bipartite if the nodes of the graph 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.
``````
##### For Example,
``````If βNβ = 4, βMβ = 5, edgeList = [ [0, 1],[0, 3],[1, 2] ].
``````

``````Here, you can see that the graph is bipartite as we can divide the nodes in two sets as follows:
setA = [0, 2].
setB = [1, 3].

In the graph, you can see that every edge in the graph connects a node in set A and a node in set B.
Hence, the output is βYesβ.
``````
Detailed explanation ( Input/output format, Notes, Images )
##### Constraints:
``````1 <= T <= 10
1 <= N <= 500
1 <= M <= (N * (N - 1)) / 2

Time limit: 1 sec
``````
##### Sample Input 1 :
``````2
4 3
0 1
0 3
1 2
4 5
0 1
0 3
1 2
2 3
0 2
``````
##### Sample output 1 :
``````Yes
No
``````
##### Explanation For Sample Output 1:
``````For the first test case, the graph will be:
``````

``````Here, you can see that the graph is bipartite as we can divide the nodes into two sets as follows:
setA = [0, 2].
setB = [1, 3].

In the graph, you can see that every edge in the graph connects a node in set A and a node in set B.
Hence, the output is βYesβ.

For the second test case, the graph will be:
``````

``````Here, you cannot divide the nodes 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. Hence, the output is βNoβ.
``````
##### Sample Input 2 :
``````2
4 4
0 1
0 2
0 3
2 3
3 3
0 2
1 0
1 2
``````
##### Sample output 2 :
``````No
No
``````
Autocomplete
Console