Largest subset of Graph vertices with edges of 2 or more colors | Java 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 code
import java . util . * ; class GFG { static int N = 6 ; static int subsetGraph ( int C [ ] [ ] ) { HashSet < Integer > vertices = new HashSet < > ( ) ; for ( int i = 0 ; i < N ; ++ i ) { vertices . add ( i ) ; } while ( ! vertices . isEmpty ( ) ) { if ( vertices . size ( ) == 1 ) { return 1 ; } boolean someone_removed = false ; for ( int x : vertices ) { HashSet < Integer > values = new HashSet < > ( ) ; for ( int y : vertices ) { if ( y != x ) { values . add ( C [ x ] [ y ] ) ; } } if ( values . size ( ) == 1 ) { vertices . remove ( x ) ; someone_removed = true ; break ; } } if ( ! someone_removed ) { break ; } } return ( vertices . size ( ) ) ; } public static void main ( String [ ] args ) { int 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 } } ; System . out . println ( subsetGraph ( C ) ) ; } }