m Coloring Problem | Backtracking | C # 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { class node { public int color = 1 ; public HashSet < int > edges = new HashSet < int > ( ) ; } ; static int canPaint ( List < node > nodes , int n , int m ) { List < int > visited = new List < int > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { visited . Add ( 0 ) ; } int maxColors = 1 ; for ( int sv = 1 ; sv <= n ; sv ++ ) { if ( visited [ sv ] > 0 ) continue ; visited [ sv ] = 1 ; Queue q = new Queue ( ) ; q . Enqueue ( sv ) ; while ( q . Count != 0 ) { int top = ( int ) q . Peek ( ) ; q . Dequeue ( ) ; foreach ( int it in 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 . Enqueue ( it ) ; } } } } return 1 ; } public static void Main ( ) { int n = 4 ; int [ , ] graph = { { 0 , 1 , 1 , 1 } , { 1 , 0 , 1 , 0 } , { 1 , 1 , 0 , 1 } , { 1 , 0 , 1 , 0 } } ; int m = 3 ; List < node > nodes = new List < 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 [ i ] . edges . Add ( i ) ; nodes [ j ] . edges . Add ( j ) ; } } } Console . WriteLine ( canPaint ( nodes , n , m ) ) ; } }