m Coloring Problem | Backtracking | Javascript 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 ; Number of colors ; Create a vector of n + 1 nodes of type " node " The zeroth position is just dummy ( 1 to n to be used ) ; Push edges to each node as per given input ; Connect the undirected graph ; Display final answer
class node { constructor ( ) { this . color = 1 ; this . edges = new Set ( ) ; } } ; function canPaint ( nodes , n , m ) { var visited = [ ] ; for ( var i = 0 ; i < n + 1 ; i ++ ) { visited . push ( 0 ) ; } var maxColors = 1 ; for ( var sv = 1 ; sv <= n ; sv ++ ) { if ( visited [ sv ] > 0 ) continue ; visited [ sv ] = 1 ; var q = [ ] ; q . push ( sv ) ; while ( q . length != 0 ) { var top = q [ 0 ] ; q . shift ( ) ; for ( var it of nodes [ top ] . edges ) { if ( nodes [ top ] . color == nodes [ it ] . color ) nodes [ it ] . color += 1 ; maxColors = Math . max ( maxColors , Math . max ( nodes [ top ] . color , nodes [ it ] . color ) ) ; if ( maxColors > m ) return 0 ; if ( visited [ it ] == 0 ) { visited [ it ] = 1 ; q . push ( it ) ; } } } } return 1 ; } var n = 4 ; var graph = [ [ 0 , 1 , 1 , 1 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 1 , 0 , 1 ] , [ 1 , 0 , 1 , 0 ] ] ; var m = 3 ; var nodes = [ ] ; for ( var i = 0 ; i < n + 1 ; i ++ ) { nodes . push ( new node ( ) ) ; } for ( var i = 0 ; i < n ; i ++ ) { for ( var j = 0 ; j < n ; j ++ ) { if ( graph [ i , j ] > 0 ) { nodes [ i ] . edges . push ( i ) ; nodes [ j ] . edges . push ( j ) ; } } } document . write ( canPaint ( nodes , n , m ) ) ;