m Coloring Problem | Backtracking | CPP 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
#include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; class node { public : int color = 1 ; set < int > edges ; } ; int canPaint ( vector < node > & nodes , int n , int m ) { vector < int > visited ( n + 1 , 0 ) ; int maxColors = 1 ; for ( int sv = 1 ; sv <= n ; sv ++ ) { if ( visited [ sv ] ) continue ; visited [ sv ] = 1 ; queue < int > q ; q . push ( sv ) ; while ( ! q . empty ( ) ) { int top = q . front ( ) ; q . pop ( ) ; for ( auto it = nodes [ top ] . edges . begin ( ) ; it != nodes [ top ] . edges . end ( ) ; it ++ ) { if ( nodes [ top ] . color == nodes [ * it ] . color ) nodes [ * it ] . color += 1 ; maxColors = max ( maxColors , max ( nodes [ top ] . color , nodes [ * it ] . color ) ) ; if ( maxColors > m ) return 0 ; if ( ! visited [ * it ] ) { visited [ * it ] = 1 ; q . push ( * it ) ; } } } } return 1 ; } int main ( ) { int n = 4 ; bool graph [ n ] [ n ] = { { 0 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 } , { 1 , 1 , 0 , 1 } , { 1 , 0 , 1 , 0 } } ; vector < node > nodes ( n + 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( graph [ i ] [ j ] ) { nodes [ i ] . edges . insert ( i ) ; nodes [ j ] . edges . insert ( j ) ; } } } cout << canPaint ( nodes , n , m ) ; cout << " STRNEWLINE " ; return 0 ; }