Is Bipartite
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”.

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

Question

Is Bipartite

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”.

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

Accepted Answer

I solved this question by using BFS.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O( 1 )

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

Time Complexity: OtherExplanation:

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).

Accepted Answer

Recursive Approach (Dfs).

Approach:

If we fix the Set of node ‘x’, let’s say it belongs to Set A then the nodes which are immediate neighbors of the node ‘x’ should belong to Set B as, if they belong to the Set A then the condition of bipartite fails. The same condition can be applied for the nodes which are immediate neighbors of the node ‘x’. So, after fixing the Set of any node in the connected component of the graph, the Set of all the other nodes will be fixed.

Let's denote Set A by 0 and Set B by 1. For every node which is not been visited yet, we run a recursive function check(node, c, adj, color, vis),(where “node” is the current node we are at, ‘c’ either 0 or 1, denoting the set of the “node”, “adj” is the adjacency list of all the nodes, adjacency list stores all the nodes which are directly connected to the ith node,” color ” is the vector which tells the Set of the ith node, “vis” is the vector which keeps track of every node whether it has been traversed or not) and try to assign Set to every node in its connected component if 2 nodes that are immediate neighbors are in the same Set then we will return false.

Here is the algorithm:

check function:
- Assign color to node, color[node] = c.
- Mark the node visited, vis[node] = 1.
- Traverse the adjacency list of the current node “node” (say iterator ‘i’)
  - If adj[node][i] is not visited
    - if( ! check( adj [node][i], c^1, adj, color, vis) ) , graph is not bipartite
      - Return False.
  - Else
    - If color[adj[node][i]] is equal to ‘c’
      - Return False.
- Return True.

given function:
- Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
- Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
- Declare a vector “color” for marking the Set each node corresponds to, “vis” for marking nodes visited.
- For every node from 0 to ‘n’ -1 (say iterator ‘i’)
  - If node ‘i’ is not visited
    - If the condition of the bipartite graph fails
      - Return false.
Return true.

Space Complexity: O(n)Explanation:

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

Extra space used by adjacency list “ADJ” is of size O(N + M), and recursion stack, list “VISITED”, “COLOR” use O(N) space, Thus overall space complexity will be O(N + M).

Time Complexity: O(n)Explanation:

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

The “check” function takes O(N + M) time in the worst case and creating an adjacency list will also take O(N + M) times, Thus overall time complexity will be O(N + M).

Java (SE 1.8)

/*
    Time Complexity : O(N + M).
    Space Complexity : O(N + M).

    Where N is the number of nodes and M is the number of edges.
*/

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

	private static ArrayList> adj;

	private static boolean check(int node, int c, int[] color, int[] vis) {
		// Assign color to the node.
		color[node] = c;
		// Mark the node visited.
		vis[node] = 1;

		// Iterate over the adjacency list of the node.
		for (int i = 0; i < adj.get(node).size(); i++) {
			if (vis[adj.get(node).get(i)] == 0) {
				if (!check(adj.get(node).get(i), c ^ 1, color, vis)) {
					return false;
				}
			} else {
				// Detection of odd length cycle.
				if (color[adj.get(node).get(i)] == c) {
					return false;
				}
			}
		}

		return true;
	}

	public static Boolean isBipartite(int n, int edges[][]) {

		// Create adjacency list.
		adj = new ArrayList>(n);
		for (int i = 0; i < n; i++) {
			ArrayList temp = new ArrayList();
			adj.add(temp);
		}
		for (int i = 0; i < edges.length; i++) {
			int u = edges[i][0];
			int v = edges[i][1];
			adj.get(u).add(v);
			adj.get(v).add(u);
		}
		// Initialize "color" and "vis" vector.
		int color[] = new int[n];
		int vis[] = new int[n];
		Arrays.fill(color, -1);
		Arrays.fill(vis, 0);

		/*
		 * Checking for every component of the graph as the graph can also
		 * be disconnected.
		 */
		for (int i = 0; i < n; i++) {
			if (vis[i] == 0) {
				if (!check(i, 0, color, vis)) {
					// Return false as the graph is not Bipartite.
					return false;
				}
			}
		}

		// Return true as the graph is Bipartite.

		return true;
	}
}

Python (3.5)

'''
    Time Complexity : O(N + M).
    Space Complexity : O(N + M).

    Where ‘N’ is the number of nodes and ‘M’ is the number of edges.
'''

from typing import List

def check(node: int, c: int, adj: List[List[int]], color: List[int], vis: List[int]) -> bool:

    # Assign color to the node.
    color[node] = c
    # Mark the node visited.
    vis[node] = 1

    # Iterate over the adjacency list of the node.
    for i in range(len(adj[node])):
    
        if not vis[adj[node][i]]:
            if not check(adj[node][i], c ^ 1, adj, color, vis):
                return False
            
        else:
            # Detection of odd length cycle.
            if color[adj[node][i]] == c:
                return False

    return True


def isBipartite(n: int, edges: List[List[int]]) -> bool:

    # Create adjacency list.
    adj = [[] for _ in range(n)]
    
    for i in range(len(edges)):
    
        u = edges[i][0]
        v = edges[i][1]
        adj[u].append(v)
        adj[v].append(u)
    
    # Initialize "color" and "vis" vector.
    color = [-1 for _ in range(n)]
    vis = [0 for _ in range(n)]

    '''
        Checking for every component of the graph as the graph can also
        be disconnected.
    '''
    for i in range(n):

        if not vis[i]:
            if not check(i, 0, adj, color, vis):
                # Return false as the graph is not Bipartite.
                return False

    # Return true as the graph is Bipartite.
    return True

C++ (g++ 5.4)

/*



    Time Complexity : O(N + M).

    Space Complexity : O(N + M).



    Where ‘N’ is the number of nodes and ‘M’ is the number of edges.



*/



bool check(int node, int c, vector> &adj, vector &color, vector &vis)

{



    // Assign color to the node.

    color[node] = c;

    // Mark the node visited.

    vis[node] = 1;



    // Iterate over the adjacency list of the node.

    for (int i = 0; i < adj[node].size(); i++)

    {

        if (!vis[adj[node][i]])

        {

            if (!check(adj[node][i], c ^ 1, adj, color, vis))

            {

                return false;

            }

        }

        else

        {

            // Detection of odd length cycle.

            if (color[adj[node][i]] == c)

            {

                return false;

            }

        }

    }



    return true;

}



bool isBipartite(int n, vector> &edges)

{



    // Create adjacency list.

    vector> adj(n);

    for (int i = 0; i < edges.size(); i++)

    {

        int u = edges[i][0];

        int v = edges[i][1];

        adj[u].push_back(v);

        adj[v].push_back(u);

    }

    // Initialize "color" and "vis" vector.

    vector color(n, -1);

    vector vis(n);



    /*

    Checking for every component of the graph as the graph can also

    be disconnected.

    */

    for (int i = 0; i < n; i++)

    {

        if (!vis[i])

        {

            if (!check(i, 0, adj, color, vis))

            {

                // Return false as the graph is not Bipartite.

                return false;

            }

        }

    }



    // Return true as the graph is Bipartite.



    return true;

}

Accepted Answer

Iterative Approach (Bfs)

Approach:

The basic idea of this approach is similar to the idea of approach 2 the only difference is that in approach 1 we use a recursive approach to assign Set to every node here we will be doing this iteratively with the help of Bfs that is we will be doing level order traversal.

For the implementation of this approach we will be using a data-structure “queue” as we want level order traversal so if a node ‘x' enters before a node “y” in the queue then “x” will be processed before “y”.

The idea of this approach is to traverse the graph in level order starting from the “source” node and putting in node “source” in Set A and explore all the neighboring nodes, if the neighboring node is not visited yet then we will make it visited, put this node in Set B and put in into “queue” otherwise we have to check the Set of the node, let say “x”, which has been visited. If the “source” node has the same set as the node “x” then the graph is not bipartite and we will return false otherwise continue the above process until the “queue” is not empty.

As the graph may not be connected we have to do the above-discussed algorithm for every connected component of the graph.

Here is the algorithm:

Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
Declare a vector “vis” for marking nodes visited.
Declare a vector “color” for marking the Set of each node.
Declare a queue to perform “Bfs”.
For every node from 0 to ‘n’ -1 (say iterator ‘i’)
- If node ‘i’ is not visited
  - Push the node ‘i’ in the queue, mark the node visited, and mark the set of node ‘i’ to 0.
  - while(queue is not empty)
    - Node = queue.front().
    - Pop node “node” from the queue.
    - Traverse the adjacency list of the current node “node” (say iterator ‘i’)
      - If adj[node][i] is not visited
        Push adj[node][i] in the queue.
        Mark adj[node][i] visited.
        Make the set opposite to node “node”.
      - Else
        If color[adj[node][i]] is equal to color[node]
        Return False.
Return True.

Space Complexity: O(n)Explanation:

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

Extra space used by the adjacency list “ADJ” is of size O(N + M). “QUEUE”, “COLOR” and ”VISITED” use O(N) space, Thus overall space complexity will be O(N + M).

Time Complexity: O(n)Explanation:

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

“BFS” function takes O(N + M) time in the worst case and creating an adjacency list will also take O(N + M) time, Thus overall time complexity will be O(N + M).

Java (SE 1.8)

/*
    Time Complexity : O(N + M).
    Space Complexity : O(N + M).

    Where N is the number of nodes and M is the number of edges.
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static Boolean isBipartite(int n, int edges[][]) {

        // Create adjacency list.
        ArrayList> adj = new ArrayList>(n);
        for (int i = 0; i < n; i++) {
            ArrayList temp = new ArrayList();
            adj.add(temp);
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        // Initialize "color" and "vis" vector.
        int color[] = new int[n];
        int vis[] = new int[n];
        Arrays.fill(color, -1);

        // Declare "queue" to perform bfs.
        Queue que = new LinkedList();
        /*
         * Checking for every component of the graph as the graph can also
         * be disconnected.
         */
        for (int i = 0; i < n; i++) {
            if (vis[i] == 0) {

                que.add(i);
                vis[i] = 1;
                color[i] = 0;
                while (que.size() > 0) {
                    int node = que.poll();
                    for (int j = 0; j < adj.get(node).size(); j++) {
                        if (vis[adj.get(node).get(j)] == 0) {
                            // Mark the node visited and push it into the queue.
                            vis[adj.get(node).get(j)] = 1;
                            que.add(adj.get(node).get(j));
                            // Color the node opposite the color of the node "a".
                            color[adj.get(node).get(j)] = color[node] ^ 1;
                        } else {
                            // Return false as the color of 2 adjacent nodes are same.
                            if (color[adj.get(node).get(j)] == color[node])
                                return false;
                        }
                    }
                }
            }
        }
        // Return true as the graph is Bipartite.

        return true;
    }
}

Python (3.5)

'''
    Time Complexity : O(N + M).
    Space Complexity : O(N + M).

    Where ‘N’ is the number of nodes and ‘M’ is the number of edges.
'''

from typing import List
from queue import Queue

def isBipartite(n: int, edges: List[List[int]]) -> bool:

    # Create adjacency list.
    adj = [[] for _ in range(n)]

    for i in range(len(edges)):
    
        u = edges[i][0]
        v = edges[i][1]
        adj[u].append(v)
        adj[v].append(u)
    
    # Initialize "color" and "vis" vector.
    color = [-1 for _ in range(n)]
    vis = [False for _ in range(n)]

    # Declare "queue" to perform bfs.
    que = Queue()
    '''
        Checking for every component of the graph as the graph can also
        be disconnected.
    '''
    for i in range(n):
    
        if vis[i] == 0:

            que.put(i)
            vis[i] = 1
            color[i] = 0
            while not que.empty():
            
                node = que.get()
                
                for i in range(len(adj[node])):
                
                    if vis[adj[node][i]] == 0:
                    
                        # Mark the node visited and push it into the queue.
                        vis[adj[node][i]] = 1, que.put(adj[node][i])
                        # Color the node opposite the color of the node "a".
                        color[adj[node][i]] = color[node] ^ 1
                    
                    else:
                    
                        # Return false as the color of 2 adjacent nodes are same.
                        if color[adj[node][i]] == color[node]:
                            return False

    # Return true as the graph is Bipartite.
    return True

C++ (g++ 5.4)

/*



    Time Complexity : O(N + M).

    Space Complexity : O(N + M).



    Where ‘N’ is the number of nodes and ‘M’ is the number of edges.



*/



bool isBipartite(int n, vector> &edges)

{



    // Create adjacency list.

    vector> adj(n);

    for (int i = 0; i < edges.size(); i++)

    {

        int u = edges[i][0];

        int v = edges[i][1];

        adj[u].push_back(v);

        adj[v].push_back(u);

    }

    // Initialize "color" and "vis" vector.

    vector color(n, -1);

    vector vis(n);



    // Declare "queue" to perform bfs.

    queue que;

    /*

    Checking for every component of the graph as the graph can also

    be disconnected.

    */

    for (int i = 0; i < n; i++)

    {

        if (vis[i] == 0)

        {



            que.push(i);

            vis[i] = 1;

            color[i] = 0;

            while (!que.empty())

            {

                int node = que.front();

                que.pop();

                for (int i = 0; i < adj[node].size(); i++)

                {

                    if (vis[adj[node][i]] == 0)

                    {

                        // Mark the node visited and push it into the queue.

                        vis[adj[node][i]] = 1, que.push(adj[node][i]);

                        // Color the node opposite the color of the node "a".

                        color[adj[node][i]] = color[node] ^ 1;

                    }

                    else

                    {

                        // Return false as the color of 2 adjacent nodes are same.

                        if (color[adj[node][i]] == color[node])

                            return false;

                    }

                }

            }

        }

    }

    // Return true as the graph is Bipartite.



    return true;

}

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:

For Example,

Input Format :

Output Format :

Note :

Constraints:

Top MindTickle Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern