Bipartite Graph

Given an adjacency list of a graph adj  of V no. of vertices having 0 based index. Check whether the graph is bipartite or not.

graph is a bipartite if it can be coloured in two ways

Example 1:

         

input:
0 is connected to 1 and 2
1 is connected to 0
2 is connected to 0



Output: 1
Explanation: The given graph can be colored 
in two colors so, it is a bipartite graph.

Example 2:

Input:
              

0 is connected to 2 and 3
1 is connected to 3
2 is connected to 0 and 3
3 is connected to 0, 1 and 2

Output: 0

c++ implementation:

// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
class Solution {
public:

//the main bipartite program starts here
    bool dfs(int n,vector<int>a[],int vis[],int col[],int x,int c)
    {
        col[x]=c;
        
        for(auto y:a[x])
        {
            if(col[y]==-1)
            {
                if(dfs(n,a,vis,col,y,!c)==0)
                return 0;
            }
            else
            {
                if(col[x]==col[y])
                return 0;
            }
        }
        return 1;
    }
	bool isBipartite(int n, vector<int>a[]){
	    int vis[n];int col[n];
	    
	    for(int i=0;i<n;i++)
	    {
	        vis[i]=0;
	        col[i]=-1;
	    }
	    
	    for(int i=0;i<n;i++)
	    {
	        if(col[i]==-1)
	        {
	             if(dfs(n,a,vis,col,i,0)==0)
	             return 0;
	        }
	   
	    }
	    return 1;
	    
	}
//------------
};

// { Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int V, E;
		cin >> V >> E;
		vector<int>adj[V];
		for(int i = 0; i < E; i++){
			int u, v;
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		Solution obj;
		bool ans = obj.isBipartite(V, adj);    
		if(ans)cout << "1\n";
		else cout << "0\n";  
	}
	return 0;
}  // } Driver Code Ends

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
• Space Complexity :O(V). 
  Since an extra visited array is needed of size V.