Minimum colors required such that edges forming cycle do not have same color | Java 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
import java . util . * ; class GFG { static int n = 5 , m = 7 ; static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static Vector < pair > [ ] g = new Vector [ m ] ; static int [ ] col = new int [ n ] ; static boolean cyc ; static int [ ] res = new int [ m ] ; static void dfs ( int v ) { col [ v ] = 1 ; for ( pair p : g [ v ] ) { int to = p . first , id = p . second ; 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 ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < m ; i ++ ) g [ i ] = new Vector < pair > ( ) ; g [ 0 ] . add ( new pair ( 1 , 0 ) ) ; g [ 0 ] . add ( new pair ( 2 , 1 ) ) ; g [ 1 ] . add ( new pair ( 2 , 2 ) ) ; g [ 1 ] . add ( new pair ( 3 , 3 ) ) ; g [ 2 ] . add ( new pair ( 3 , 4 ) ) ; g [ 3 ] . add ( new pair ( 4 , 5 ) ) ; g [ 4 ] . add ( new pair ( 2 , 6 ) ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( col [ i ] == 0 ) { dfs ( i ) ; } } System . out . print ( ( cyc ? 2 : 1 ) + "NEW_LINE"); for ( int i = 0 ; i < m ; ++ i ) { System . out . print ( res [ i ] + " ▁ " ) ; } } }