m Coloring Problem | Backtracking | Java program for the above approach ; A node class which stores the color and the edges connected to the node ; Create a visited array of n nodes , initialized to zero ; maxColors used till now are 1 as all nodes are painted color 1 ; Do a full BFS traversal from all unvisited starting points ; If the starting point is unvisited , mark it visited and push it in queue ; BFS Travel starts here ; Checking all adjacent nodes to " top " edge in our queue ; IMPORTANT : If the color of the adjacent node is same , increase it by 1 ; If number of colors used shoots m , return 0 ; If the adjacent node is not visited , mark it visited and push it in queue ; Driver code ; Create a vector of n + 1 nodes of type " node " The zeroth position is just dummy ( 1 to n to be used ) ; Add edges to each node as per given input ; Connect the undirected graph ; Display final answer
import java . io . * ; import java . util . * ; class Node { int color = 1 ; Set < Integer > edges = new HashSet < Integer > ( ) ; } class GFG { static int canPaint ( ArrayList < Node > nodes , int n , int m ) { ArrayList < Integer > visited = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { visited . add ( 0 ) ; } int maxColors = 1 ; for ( int sv = 1 ; sv <= n ; sv ++ ) { if ( visited . get ( sv ) > 0 ) { continue ; } visited . set ( sv , 1 ) ; Queue < Integer > q = new LinkedList < > ( ) ; q . add ( sv ) ; while ( q . size ( ) != 0 ) { int top = q . peek ( ) ; q . remove ( ) ; for ( int it : nodes . get ( top ) . edges ) { if ( nodes . get ( top ) . color == nodes . get ( it ) . color ) { nodes . get ( it ) . color += 1 ; } maxColors = Math . max ( maxColors , Math . max ( nodes . get ( top ) . color , nodes . get ( it ) . color ) ) ; if ( maxColors > m ) return 0 ; if ( visited . get ( it ) == 0 ) { visited . set ( it , 1 ) ; q . remove ( it ) ; } } } } return 1 ; } public static void main ( String [ ] args ) { int n = 4 ; int [ ] [ ] graph = { { 0 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 } , { 1 , 1 , 0 , 1 } , { 1 , 0 , 1 , 0 } } ; ArrayList < Node > nodes = new ArrayList < Node > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { nodes . add ( new Node ( ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( graph [ i ] [ j ] > 0 ) { nodes . get ( i ) . edges . add ( i ) ; nodes . get ( j ) . edges . add ( j ) ; } } } System . out . println ( canPaint ( nodes , n , m ) ) ; } }