Is Graph Bipartite?

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in companies
FacebookSamsungDirecti

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 )
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 :
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
Hint

Try all possible combinations of dividing the nodes into 2 sets.

Approaches (3)
Brute Force

Approach: 

 

The idea is to try out all possible combinations of dividing the nodes into 2 Sets and try to find a combination that satisfies the condition of a bipartite graph.

 

For that, we will be using the concept of bit masking. Let’s take ‘N’ = 3 and an integer ‘X’ = 5.

The binary representation of 5 is “101” which implies that nodes 1,3 are in set A and node 2 is in set B, in “101”  node 1 is the LSB, and node 3 is MSB. Nodes that have their corresponding bits set are put in Set A and the remaining nodes in Set B. 

 

So, if a graph has ‘N’ nodes we need to have an integer that has its binary representation ‘n’ bits long, which is (2^n)-1. So, every integer from 0 to (2^n)-1 represents a different combination of dividing the nodes into 2 Sets.
 

Now, after dividing the nodes into two Sets we just have to check that for every given edge of the graph the two nodes are in different sets or not, for that we just have to look at their corresponding bits if they both are set or unset means that they are in the same set otherwise not.

 

Here is the algorithm:

 

  • Run a loop from 0 to (2^n)-1 (say iterator ‘i’)
    • Initialize a variable “flag”=0, “flag” is equal to 0 means the graph is bipartite otherwise not.
      • Iterate over the edges of the given graph (say iterator ‘j’)  and check whether the 2 nodes lie in the same set or not.
        • If both lie in the same then set a flag to 1 and break from the loop as the graph is not bipartite.
    • If the flag is equal to 0 means the graph is bipartite so return True.
  • Return False.
Time Complexity

O( (2 ^ N) * M ), where ‘N’ is the number of nodes and ‘M’ is the number of edges.
 

There are 2^N possible combinations and for each combination, we have to check all the edges. Hence the overall time complexity will be O((2 ^ N) * M).

Space Complexity

O( 1 )

 

As we are not using any kind of extra space. Hence the overall space complexity will be O( 1 ).

Code Solution
(100% EXP penalty)
Is Graph Bipartite?
Full screen
Console