m Coloring Problem | Backtracking | Python3 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 ) ; Add edges to each node as per given input ; Connect the undirected graph ; Display final answer
from queue import Queue NEW_LINE class node : NEW_LINE INDENT color = 1 NEW_LINE edges = set ( ) NEW_LINE DEDENT def canPaint ( nodes , n , m ) : NEW_LINE INDENT visited = [ 0 for _ in range ( n + 1 ) ] NEW_LINE maxColors = 1 NEW_LINE for _ in range ( 1 , n + 1 ) : NEW_LINE INDENT if visited [ _ ] : NEW_LINE INDENT continue NEW_LINE DEDENT visited [ _ ] = 1 NEW_LINE q = Queue ( ) NEW_LINE q . put ( _ ) NEW_LINE while not q . empty ( ) : NEW_LINE INDENT top = q . get ( ) NEW_LINE for _ in nodes [ top ] . edges : NEW_LINE INDENT if nodes [ top ] . color == nodes [ _ ] . color : NEW_LINE INDENT nodes [ _ ] . color += 1 NEW_LINE DEDENT maxColors = max ( maxColors , max ( nodes [ top ] . color , nodes [ _ ] . color ) ) NEW_LINE if maxColors > m : NEW_LINE INDENT print ( maxColors ) NEW_LINE return 0 NEW_LINE DEDENT if not visited [ _ ] : NEW_LINE INDENT visited [ _ ] = 1 NEW_LINE q . put ( _ ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE graph = [ [ 0 , 1 , 1 , 1 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 1 , 0 , 1 ] , [ 1 , 0 , 1 , 0 ] ] NEW_LINE m = 3 NEW_LINE nodes = [ ] NEW_LINE for _ in range ( n + 1 ) : NEW_LINE INDENT nodes . append ( node ( ) ) NEW_LINE DEDENT for _ in range ( n ) : NEW_LINE INDENT for __ in range ( n ) : NEW_LINE INDENT if graph [ _ ] [ __ ] : NEW_LINE INDENT nodes [ _ ] . edges . add ( _ ) NEW_LINE nodes [ __ ] . edges . add ( __ ) NEW_LINE DEDENT DEDENT DEDENT print ( canPaint ( nodes , n , m ) ) NEW_LINE DEDENT