Node whose removal minimizes the maximum size forest from an N | JavaScript program to implement the above approach ; Function to create the graph ; Function to traverse the graph and find the minimum of Math . maximum size forest after removing a node ; Traversing every child subtree except the parent node ; Traverse all subtrees ; Update the Math . maximum size of forests ; Update the minimum of Math . maximum size of forests obtained ; Condition to find the minimum of Math . maximum size forest ; Update and store the corresponding node ; Driver Code
var mini = 105 , ans , n ; var g = Array . from ( Array ( 100 ) , ( ) => new Array ( ) ) ; var size = Array ( 100 ) . fill ( 0 ) ; function create_graph ( ) { g [ 1 ] . push ( 2 ) ; g [ 2 ] . push ( 1 ) ; g [ 1 ] . push ( 3 ) ; g [ 3 ] . push ( 1 ) ; g [ 1 ] . push ( 4 ) ; g [ 4 ] . push ( 1 ) ; g [ 2 ] . push ( 5 ) ; g [ 5 ] . push ( 2 ) ; g [ 2 ] . push ( 6 ) ; g [ 6 ] . push ( 2 ) ; } function dfs ( node , parent ) { size [ node ] = 1 ; var mx = 0 ; g [ node ] . forEach ( y => { if ( y != parent ) { dfs ( y , node ) ; size [ node ] += size [ y ] ; mx = Math . max ( mx , size [ y ] ) ; } } ) ; mx = Math . max ( mx , n - size [ node ] ) ; if ( mx < mini ) { mini = mx ; ans = node ; } } n = 6 ; create_graph ( ) ; dfs ( 1 , - 1 ) ; document . write ( ans ) ;