Minimum colors required such that edges forming cycle do not have same color | Python3 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
n = 5 NEW_LINE m = 7 ; NEW_LINE g = [ [ ] for i in range ( m ) ] NEW_LINE col = [ 0 for i in range ( n ) ] ; NEW_LINE cyc = True NEW_LINE res = [ 0 for i in range ( m ) ] ; NEW_LINE def dfs ( v ) : NEW_LINE INDENT col [ v ] = 1 ; NEW_LINE for p in g [ v ] : NEW_LINE INDENT to = p [ 0 ] NEW_LINE id = p [ 1 ] ; NEW_LINE if ( col [ to ] == 0 ) : NEW_LINE INDENT dfs ( to ) ; NEW_LINE res [ id ] = 1 ; NEW_LINE DEDENT elif ( col [ to ] == 2 ) : NEW_LINE INDENT res [ id ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT res [ id ] = 2 ; NEW_LINE cyc = True ; NEW_LINE DEDENT DEDENT col [ v ] = 2 ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT g [ 0 ] . append ( [ 1 , 0 ] ) ; NEW_LINE g [ 0 ] . append ( [ 2 , 1 ] ) ; NEW_LINE g [ 1 ] . append ( [ 2 , 2 ] ) ; NEW_LINE g [ 1 ] . append ( [ 3 , 3 ] ) ; NEW_LINE g [ 2 ] . append ( [ 3 , 4 ] ) ; NEW_LINE g [ 3 ] . append ( [ 4 , 5 ] ) ; NEW_LINE g [ 4 ] . append ( [ 2 , 6 ] ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( col [ i ] == 0 ) : NEW_LINE INDENT dfs ( i ) ; NEW_LINE DEDENT DEDENT print ( 2 if cyc else 1 ) NEW_LINE for i in range ( m ) : NEW_LINE INDENT print ( res [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT