Largest subset of Graph vertices with edges of 2 or more colors | Number of vertices ; function to calculate max subset size ; set for number of vertices ; loop for deletion of vertex from set ; if subset has only 1 vertex return 0 ; for each vertex iterate and keep removing a vertix while we find a vertex with all edges of same color . ; note down different color values for each vertex ; if only one color is found erase that vertex ( bad vertex ) ; If no vertex was removed in the above loop . ; Driver Code
N = 6 NEW_LINE def subsetGraph ( C ) : NEW_LINE INDENT global N NEW_LINE vertices = set ( ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT vertices . add ( i ) NEW_LINE DEDENT while ( len ( vertices ) != 0 ) : NEW_LINE INDENT if ( len ( vertices ) == 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT someone_removed = False NEW_LINE for x in vertices : NEW_LINE INDENT values = set ( ) NEW_LINE for y in vertices : NEW_LINE INDENT if ( y != x ) : NEW_LINE INDENT values . add ( C [ x ] [ y ] ) NEW_LINE DEDENT DEDENT if ( len ( values ) == 1 ) : NEW_LINE INDENT vertices . remove ( x ) NEW_LINE someone_removed = True NEW_LINE break NEW_LINE DEDENT DEDENT if ( not someone_removed ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return len ( vertices ) NEW_LINE DEDENT C = [ [ 0 , 9 , 2 , 4 , 7 , 8 ] , [ 9 , 0 , 9 , 9 , 7 , 9 ] , [ 2 , 9 , 0 , 3 , 7 , 6 ] , [ 4 , 9 , 3 , 0 , 7 , 1 ] , [ 7 , 7 , 7 , 7 , 0 , 7 ] , [ 8 , 9 , 6 , 1 , 7 , 0 ] ] NEW_LINE print ( subsetGraph ( C ) ) NEW_LINE