Node whose removal minimizes the maximum size forest from an N | Java 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
import java . util . * ; class GFG { static int mini = 105 , ans , n ; static Vector < Integer > [ ] g = new Vector [ 100 ] ; static int [ ] size = new int [ 100 ] ; static void create_graph ( ) { g [ 1 ] . add ( 2 ) ; g [ 2 ] . add ( 1 ) ; g [ 1 ] . add ( 3 ) ; g [ 3 ] . add ( 1 ) ; g [ 1 ] . add ( 4 ) ; g [ 4 ] . add ( 1 ) ; g [ 2 ] . add ( 5 ) ; g [ 5 ] . add ( 2 ) ; g [ 2 ] . add ( 6 ) ; g [ 6 ] . add ( 2 ) ; } static void dfs ( int node , int parent ) { size [ node ] = 1 ; int mx = 0 ; for ( int y : g [ node ] ) { if ( y == parent ) continue ; 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 ; } } public static void main ( String [ ] args ) { n = 6 ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new Vector < Integer > ( ) ; create_graph ( ) ; dfs ( 1 , - 1 ) ; System . out . print ( ans + "NEW_LINE"); } }