Two Clique Problem ( Check if Graph can be divided in two Cliques ) | C ++ program to find out whether a given graph can be converted to two Cliques or not . ; This function returns true if subgraph reachable from src is Bipartite or not . ; Create a queue ( FIFO ) of vertex numbers and enqueue source vertex for BFS traversal ; Run while there are vertices in queue ( Similar to BFS ) ; Dequeue a vertex from queue ; Find all non - colored adjacent vertices ; An edge from u to v exists and destination v is not colored ; Assign alternate color to this adjacent v of u ; An edge from u to v exists and destination v is colored with same color as u ; If we reach here , then all adjacent vertices can be colored with alternate color ; Returns true if a Graph G [ ] [ ] is Bipartite or not . Note that G may not be connected . ; Create a color array to store colors assigned to all veritces . Vertex number is used as index in this array . The value ' - 1' of colorArr [ i ] is used to indicate that no color is assigned to vertex ' i ' . The value 1 is used to indicate first color is assigned and value 0 indicates second color is assigned . ; One by one check all not yet colored vertices . ; Returns true if G can be divided into two Cliques , else false . ; Find complement of G [ ] [ ] All values are complemented except diagonal ones ; Return true if complement is Bipartite else false . ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int V = 5 ; bool isBipartiteUtil ( int G [ ] [ V ] , int src , int colorArr [ ] ) { colorArr [ src ] = 1 ; queue < int > q ; q . push ( src ) ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; for ( int v = 0 ; v < V ; ++ v ) { if ( G [ u ] [ v ] && colorArr [ v ] == -1 ) { colorArr [ v ] = 1 - colorArr [ u ] ; q . push ( v ) ; } else if ( G [ u ] [ v ] && colorArr [ v ] == colorArr [ u ] ) return false ; } } return true ; } bool isBipartite ( int G [ ] [ V ] ) { int colorArr [ V ] ; for ( int i = 0 ; i < V ; ++ i ) colorArr [ i ] = -1 ; for ( int i = 0 ; i < V ; i ++ ) if ( colorArr [ i ] == -1 ) if ( isBipartiteUtil ( G , i , colorArr ) == false ) return false ; return true ; } bool canBeDividedinTwoCliques ( int G [ ] [ V ] ) { int GC [ V ] [ V ] ; for ( int i = 0 ; i < V ; i ++ ) for ( int j = 0 ; j < V ; j ++ ) GC [ i ] [ j ] = ( i != j ) ? ! G [ i ] [ j ] : 0 ; return isBipartite ( GC ) ; } int main ( ) { int G [ ] [ V ] = { { 0 , 1 , 1 , 1 , 0 } , { 1 , 0 , 1 , 0 , 0 } , { 1 , 1 , 0 , 0 , 0 } , { 0 , 1 , 0 , 0 , 1 } , { 0 , 0 , 0 , 1 , 0 } } ; canBeDividedinTwoCliques ( G ) ? cout << " Yes " : cout << " No " ; return 0 ; }