Check whether a given graph is Bipartite or not |  ;  ; vector to store colour of vertex assiging all to - 1 i . e . uncoloured colours are either 0 or 1 for understanding take 0 as red and 1 as blue ; queue for BFS storing { vertex , colour } ; loop incase graph is not connected ; if not coloured ; colouring with 0 i . e . red ; current vertex ; colour of current vertex ; traversing vertexes connected to current vertex ; if already coloured with parent vertex color then bipartite graph is not possible ; if uncooloured ; colouring with opposite color to that of parent ; if all vertexes are coloured such that no two connected vertex have same colours ; { Driver Code Starts . ; adjacency list for storing graph ; returns 1 if bipatite graph is possible ; returns 0 if bipartite graph is not possible
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isBipartite ( int V , vector < int > adj [ ] ) { vector < int > col ( V , -1 ) ; queue < pair < int , int > > q ; for ( int i = 0 ; i < V ; i ++ ) { if ( col [ i ] == -1 ) { q . push ( { i , 0 } ) ; col [ i ] = 0 ; while ( ! q . empty ( ) ) { pair < int , int > p = q . front ( ) ; q . pop ( ) ; int v = p . first ; int c = p . second ; for ( int j : adj [ v ] ) { if ( col [ j ] == c ) return 0 ; if ( col [ j ] == -1 ) { col [ j ] = ( c ) ? 0 : 1 ; q . push ( { j , col [ j ] } ) ; } } } } } return 1 ; } int main ( ) { int V , E ; V = 4 , E = 8 ; vector < int > adj [ V ] ; adj [ 0 ] = { 1 , 3 } ; adj [ 1 ] = { 0 , 2 } ; adj [ 2 ] = { 1 , 3 } ; adj [ 3 ] = { 0 , 2 } ; bool ans = isBipartite ( V , adj ) ; if ( ans ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; return 0 ; }