New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Is Graph Bipartite?

Contributed by

KAPEESH UPADHYAY

Medium

0/80

0 upvotes

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, Constraints, Images )

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of two space-separated integers  ‘N’, ‘M’, representing the number of nodes and the number of edges of the graph.

Then next ‘M’ lines follow in each test case. The ith line consists of two space-separated integers ‘EDGES[i][0]’ and ‘EDGES[i][1]’ representing that there is a undirected edge between nodes ‘EDGES[i][0]’ and ‘EDGES[i][1]’.

Output Format :

For each test case, print the “Yes” if the given graph is bipartite, Otherwise, print “No”.

Print a separate line for each test case.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 500
1 <= M <= (N * (N - 1)) / 2

Time limit: 1 sec

Sample Input 1 :

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 :

Sample output 2 :

No
No

Auto

Console