Minimum time required to color all edges of a Tree | C ++ program for the above approach ; Stores the required answer ; Stores the graph ; Function to add edges ; Function to calculate the minimum time required to color all the edges of a tree ; Starting from time = 0 , for all the child edges ; If the edge is not visited yet . ; Time of coloring of the current edge ; If the parent edge has been colored at the same time ; Update the maximum time ; Recursively call the function to its child node ; Driver Code ; Function call ; Finally , print the answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ans = 0 ; vector < int > edges [ 100000 ] ; void Add_edge ( int u , int v ) { edges [ u ] . push_back ( v ) ; edges [ v ] . push_back ( u ) ; } void minTimeToColor ( int node , int parent , int arrival_time ) { int current_time = 0 ; for ( auto x : edges [ node ] ) { if ( x != parent ) { ++ current_time ; if ( current_time == arrival_time ) ++ current_time ; ans = max ( ans , current_time ) ; minTimeToColor ( x , node , current_time ) ; } } } int main ( ) { pair < int , int > A [ ] = { { 1 , 2 } , { 2 , 3 } , { 3 , 4 } } ; for ( auto i : A ) { Add_edge ( i . first , i . second ) ; } minTimeToColor ( 1 , -1 , 0 ) ; cout << ans << " STRNEWLINE " ; }