Two Clique Problem ( Check if Graph can be divided in two Cliques ) | Python3 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 Code
from queue import Queue NEW_LINE def isBipartiteUtil ( G , src , colorArr ) : NEW_LINE INDENT global V NEW_LINE colorArr [ src ] = 1 NEW_LINE q = Queue ( ) NEW_LINE q . put ( src ) NEW_LINE while ( not q . empty ( ) ) : NEW_LINE INDENT u = q . get ( ) NEW_LINE for v in range ( V ) : NEW_LINE INDENT if ( G [ u ] [ v ] and colorArr [ v ] == - 1 ) : NEW_LINE INDENT colorArr [ v ] = 1 - colorArr [ u ] NEW_LINE q . put ( v ) NEW_LINE DEDENT elif ( G [ u ] [ v ] and colorArr [ v ] == colorArr [ u ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT def isBipartite ( G ) : NEW_LINE INDENT global V NEW_LINE colorArr = [ - 1 ] * V NEW_LINE for i in range ( V ) : NEW_LINE INDENT if ( colorArr [ i ] == - 1 ) : NEW_LINE INDENT if ( isBipartiteUtil ( G , i , colorArr ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT def canBeDividedinTwoCliques ( G ) : NEW_LINE INDENT global V NEW_LINE GC = [ [ None ] * V for i in range ( V ) ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT GC [ i ] [ j ] = not G [ i ] [ j ] if i != j else 0 NEW_LINE DEDENT DEDENT return isBipartite ( GC ) NEW_LINE DEDENT V = 5 NEW_LINE G = [ [ 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 ] ] NEW_LINE if canBeDividedinTwoCliques ( G ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT