Minimum edge reversals to make a root | C ++ program to find min edge reversal to make every node reachable from root ; method to dfs in tree and populates disRev values ; visit current node ; looping over all neighbors ; distance of v will be one more than distance of u ; initialize back edge count same as parent node 's count ; if there is a reverse edge from u to i , then only update ; return total reversal in subtree rooted at u ; method prints root and minimum number of edge reversal ; number of nodes are one more than number of edges ; data structure to store directed tree ; disRev stores two values - distance and back edge count from root node ; add 0 weight in direction of u to v ; add 1 weight in reverse direction ; initialize all variables ; dfs populates disRev data structure and store total reverse edge counts ; for ( int i = 0 ; i < V ; i ++ ) { cout << i << " ▁ : ▁ " << disRev [ i ] . first << " ▁ " << disRev [ i ] . second << endl ; } ; loop over all nodes to choose minimum edge reversal ; ( reversal in path to i ) + ( reversal in all other tree parts ) ; choose minimum among all values ; print the designated root and total edge reversal made ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dfs ( vector < pair < int , int > > g [ ] , pair < int , int > disRev [ ] , bool visit [ ] , int u ) { visit [ u ] = true ; int totalRev = 0 ; for ( int i = 0 ; i < g [ u ] . size ( ) ; i ++ ) { int v = g [ u ] [ i ] . first ; if ( ! visit [ v ] ) { disRev [ v ] . first = disRev [ u ] . first + 1 ; disRev [ v ] . second = disRev [ u ] . second ; if ( g [ u ] [ i ] . second ) { disRev [ v ] . second = disRev [ u ] . second + 1 ; totalRev ++ ; } totalRev += dfs ( g , disRev , visit , v ) ; } } return totalRev ; } void printMinEdgeReverseForRootNode ( int edges [ ] [ 2 ] , int e ) { int V = e + 1 ; vector < pair < int , int > > g [ V ] ; pair < int , int > disRev [ V ] ; bool visit [ V ] ; int u , v ; for ( int i = 0 ; i < e ; i ++ ) { u = edges [ i ] [ 0 ] ; v = edges [ i ] [ 1 ] ; g [ u ] . push_back ( make_pair ( v , 0 ) ) ; g [ v ] . push_back ( make_pair ( u , 1 ) ) ; } for ( int i = 0 ; i < V ; i ++ ) { visit [ i ] = false ; disRev [ i ] . first = disRev [ i ] . second = 0 ; } int root = 0 ; int totalRev = dfs ( g , disRev , visit , root ) ; int res = INT_MAX ; for ( int i = 0 ; i < V ; i ++ ) { int edgesToRev = ( totalRev - disRev [ i ] . second ) + ( disRev [ i ] . first - disRev [ i ] . second ) ; if ( edgesToRev < res ) { res = edgesToRev ; root = i ; } } cout << root << " ▁ " << res << endl ; } int main ( ) { int edges [ ] [ 2 ] = { { 0 , 1 } , { 2 , 1 } , { 3 , 2 } , { 3 , 4 } , { 5 , 4 } , { 5 , 6 } , { 7 , 6 } } ; int e = sizeof ( edges ) / sizeof ( edges [ 0 ] ) ; printMinEdgeReverseForRootNode ( edges , e ) ; return 0 ; }