Largest subset of Graph vertices with edges of 2 or more colors | C ++ program to find size of subset of graph vertex such that each vertex has more than 1 color edges ; 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 6 ; int subsetGraph ( int C [ ] [ N ] ) { set < int > vertices ; for ( int i = 0 ; i < N ; ++ i ) vertices . insert ( i ) ; while ( ! vertices . empty ( ) ) { if ( vertices . size ( ) == 1 ) return 1 ; bool someone_removed = false ; for ( int x : vertices ) { set < int > values ; for ( int y : vertices ) if ( y != x ) values . insert ( C [ x ] [ y ] ) ; if ( values . size ( ) == 1 ) { vertices . erase ( x ) ; someone_removed = true ; break ; } } if ( ! someone_removed ) break ; } return ( vertices . size ( ) ) ; } int main ( ) { int C [ ] [ N ] = { { 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 } } ; cout << subsetGraph ( C ) ; return 0 ; }