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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int n = 5 , m = 7 ; vector < pair < int , int > > g [ m ] ; int col [ n ] ; bool cyc ; int res [ m ] ; void dfs ( int v ) { col [ v ] = 1 ; for ( auto 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 ; } int main ( ) { g [ 0 ] . push_back ( make_pair ( 1 , 0 ) ) ; g [ 0 ] . push_back ( make_pair ( 2 , 1 ) ) ; g [ 1 ] . push_back ( make_pair ( 2 , 2 ) ) ; g [ 1 ] . push_back ( make_pair ( 3 , 3 ) ) ; g [ 2 ] . push_back ( make_pair ( 3 , 4 ) ) ; g [ 3 ] . push_back ( make_pair ( 4 , 5 ) ) ; g [ 4 ] . push_back ( make_pair ( 2 , 6 ) ) ; for ( int i = 0 ; i < n ; ++ i ) { if ( col [ i ] == 0 ) { dfs ( i ) ; } } cout << ( cyc ? 2 : 1 ) << endl ; for ( int i = 0 ; i < m ; ++ i ) { cout << res [ i ] << ' ▁ ' ; } return 0 ; }