Minimum colors required such that edges forming cycle do not have same color | C ++ implementation to find the minimum colors required to such that edges forming cycle don 't have same color ; Variable to store the graph ; To store that the vertex is visited or not ; Boolean Value to store that graph contains cycle or not ; Variable to store the color of the edges of the graph ; Function to traverse graph using DFS Traversal ; Loop to iterate for all edges from the source vertex ; If the vertex is not visited ; Condition to check cross and forward edges of the graph ; Presence of Back Edge ; Driver Code ; Loop to run DFS Traversal on vertex which is not visited ; Loop to print the colors of the edges
const n = 5 , m = 7 ; let g = new Array ( ) ; for ( let i = 0 ; i < m ; i ++ ) { g . push ( [ ] ) } let col = new Array ( n ) . fill ( 0 ) ; let cyc ; let res = new Array ( m ) ; function dfs ( v ) { col [ v ] = 1 ; for ( let p of g [ v ] ) { let to = p [ 0 ] let id = p [ 1 ] ; if ( col [ to ] == 0 ) { dfs ( to ) ; res [ id ] = 1 ; } else if ( col [ to ] == 2 ) { res [ id ] = 1 ; } else { res [ id ] = 2 ; cyc = true ; } } col [ v ] = 2 ; } g [ 0 ] . push ( [ 1 , 0 ] ) ; g [ 0 ] . push ( [ 2 , 1 ] ) ; g [ 1 ] . push ( [ 2 , 2 ] ) ; g [ 1 ] . push ( [ 3 , 3 ] ) ; g [ 2 ] . push ( [ 3 , 4 ] ) ; g [ 3 ] . push ( [ 4 , 5 ] ) ; g [ 4 ] . push ( [ 2 , 6 ] ) ; for ( let i = 0 ; i < n ; ++ i ) { if ( col [ i ] == 0 ) { dfs ( i ) ; } } document . write ( ( cyc ? 2 : 1 ) + " " ) ; for ( let i = 0 ; i < m ; ++ i ) { document . write ( res [ i ] + ' ' ) ; }