Minimum edge reversals to make a root | C # program to find min edge reversal to make every node reachable from root ; pair class ; 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
using System ; using System . Collections . Generic ; class GFG { public class pair { public int first , second ; public pair ( int a , int b ) { first = a ; second = b ; } } static int dfs ( List < List < pair > > g , pair [ ] disRev , Boolean [ ] visit , int u ) { visit [ u ] = true ; int totalRev = 0 ; for ( int i = 0 ; i < g [ u ] . Count ; 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 != 0 ) { disRev [ v ] . second = disRev [ u ] . second + 1 ; totalRev ++ ; } totalRev += dfs ( g , disRev , visit , v ) ; } } return totalRev ; } static void printMinEdgeReverseForRootNode ( int [ , ] edges , int e ) { int V = e + 1 ; List < List < pair > > g = new List < List < pair > > ( ) ; for ( int i = 0 ; i < V + 1 ; i ++ ) g . Add ( new List < pair > ( ) ) ; pair [ ] disRev = new pair [ V ] ; for ( int i = 0 ; i < V ; i ++ ) disRev [ i ] = new pair ( 0 , 0 ) ; Boolean [ ] visit = new Boolean [ V ] ; int u , v ; for ( int i = 0 ; i < e ; i ++ ) { u = edges [ i , 0 ] ; v = edges [ i , 1 ] ; g [ u ] . Add ( new pair ( v , 0 ) ) ; g [ v ] . Add ( new 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 . MaxValue ; 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 ; } } Console . WriteLine ( root + " ▁ " + res ) ; } public static void Main ( String [ ] args ) { int [ , ] edges = { { 0 , 1 } , { 2 , 1 } , { 3 , 2 } , { 3 , 4 } , { 5 , 4 } , { 5 , 6 } , { 7 , 6 } } ; int e = edges . GetLength ( 0 ) ; printMinEdgeReverseForRootNode ( edges , e ) ; } }