Minimum edge reversals to make a root | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; pair ( int a , int b ) { first = a ; second = b ; } } static int dfs ( Vector < Vector < pair > > g , pair disRev [ ] , boolean visit [ ] , int u ) { visit [ u ] = true ; int totalRev = 0 ; for ( int i = 0 ; i < g . get ( u ) . size ( ) ; i ++ ) { int v = g . get ( u ) . get ( i ) . first ; if ( ! visit [ v ] ) { disRev [ v ] . first = disRev [ u ] . first + 1 ; disRev [ v ] . second = disRev [ u ] . second ; if ( g . get ( u ) . get ( 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 ; Vector < Vector < pair > > g = new Vector < Vector < pair > > ( ) ; for ( int i = 0 ; i < V + 1 ; i ++ ) g . add ( new Vector < 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 . get ( u ) . add ( new pair ( v , 0 ) ) ; g . get ( 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 = Integer . MAX_VALUE ; 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 ; } } System . out . println ( 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 . length ; printMinEdgeReverseForRootNode ( edges , e ) ; } }