Minimum edge reversals to make a root | Python3 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 ( i = 0 i < V i ++ ) { cout < < i < < " ▁ : ▁ " << disRev [ i ] [ 0 ] << " ▁ " << disRev [ i ] [ 1 ] << 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 sys NEW_LINE def dfs ( g , disRev , visit , u ) : NEW_LINE INDENT visit [ u ] = True NEW_LINE totalRev = 0 NEW_LINE for i in range ( len ( g [ u ] ) ) : NEW_LINE INDENT v = g [ u ] [ i ] [ 0 ] NEW_LINE if ( not visit [ v ] ) : NEW_LINE INDENT disRev [ v ] [ 0 ] = disRev [ u ] [ 0 ] + 1 NEW_LINE disRev [ v ] [ 1 ] = disRev [ u ] [ 1 ] NEW_LINE if ( g [ u ] [ i ] [ 1 ] ) : NEW_LINE INDENT disRev [ v ] [ 1 ] = disRev [ u ] [ 1 ] + 1 NEW_LINE totalRev += 1 NEW_LINE DEDENT totalRev += dfs ( g , disRev , visit , v ) NEW_LINE DEDENT DEDENT return totalRev NEW_LINE DEDENT def printMinEdgeReverseForRootNode ( edges , e ) : NEW_LINE INDENT V = e + 1 NEW_LINE g = [ [ ] for i in range ( V ) ] NEW_LINE disRev = [ [ 0 , 0 ] for i in range ( V ) ] NEW_LINE visit = [ False for i in range ( V ) ] NEW_LINE for i in range ( e ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE g [ u ] . append ( [ v , 0 ] ) NEW_LINE g [ v ] . append ( [ u , 1 ] ) NEW_LINE DEDENT for i in range ( V ) : NEW_LINE INDENT visit [ i ] = False NEW_LINE disRev [ i ] [ 0 ] = disRev [ i ] [ 1 ] = 0 NEW_LINE DEDENT root = 0 NEW_LINE totalRev = dfs ( g , disRev , visit , root ) NEW_LINE res = sys . maxsize NEW_LINE for i in range ( V ) : NEW_LINE INDENT edgesToRev = ( ( totalRev - disRev [ i ] [ 1 ] ) + ( disRev [ i ] [ 0 ] - disRev [ i ] [ 1 ] ) ) NEW_LINE if ( edgesToRev < res ) : NEW_LINE INDENT res = edgesToRev NEW_LINE root = i NEW_LINE DEDENT DEDENT print ( root , res ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT edges = [ [ 0 , 1 ] , [ 2 , 1 ] , [ 3 , 2 ] , [ 3 , 4 ] , [ 5 , 4 ] , [ 5 , 6 ] , [ 7 , 6 ] ] NEW_LINE e = len ( edges ) NEW_LINE printMinEdgeReverseForRootNode ( edges , e ) NEW_LINE DEDENT