Node whose removal minimizes the maximum size forest from an N | Python3 program to implement the above approach ; Function to create the graph ; Function to traverse the graph and find the minimum of maximum size forest after removing a Node ; Traversing every child subtree except the parent Node ; Traverse all subtrees ; Update the maximum size of forests ; Update the minimum of maximum size of forests obtained ; Condition to find the minimum of maximum size forest ; Update and store the corresponding Node ; Driver Code
mini = 105 ; NEW_LINE ans = 0 ; NEW_LINE n = 0 ; NEW_LINE g = [ ] ; NEW_LINE size = [ 0 ] * 100 ; NEW_LINE def create_graph ( ) : NEW_LINE INDENT g [ 1 ] . append ( 2 ) ; NEW_LINE g [ 2 ] . append ( 1 ) ; NEW_LINE g [ 1 ] . append ( 3 ) ; NEW_LINE g [ 3 ] . append ( 1 ) ; NEW_LINE g [ 1 ] . append ( 4 ) ; NEW_LINE g [ 4 ] . append ( 1 ) ; NEW_LINE g [ 2 ] . append ( 5 ) ; NEW_LINE g [ 5 ] . append ( 2 ) ; NEW_LINE g [ 2 ] . append ( 6 ) ; NEW_LINE g [ 6 ] . append ( 2 ) ; NEW_LINE DEDENT def dfs ( Node , parent ) : NEW_LINE INDENT size [ Node ] = 1 ; NEW_LINE mx = 0 ; NEW_LINE global mini NEW_LINE global ans NEW_LINE for y in g [ Node ] : NEW_LINE INDENT if ( y == parent ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT dfs ( y , Node ) ; NEW_LINE size [ Node ] += size [ y ] ; NEW_LINE mx = max ( mx , size [ y ] ) ; NEW_LINE DEDENT mx = max ( mx , n - size [ Node ] ) ; NEW_LINE if ( mx < mini ) : NEW_LINE INDENT mini = mx ; NEW_LINE ans = Node ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 6 ; NEW_LINE for i in range ( 100 ) : NEW_LINE INDENT g . append ( [ ] ) NEW_LINE DEDENT create_graph ( ) ; NEW_LINE dfs ( 1 , - 1 ) ; NEW_LINE print ( ans ) ; NEW_LINE DEDENT