Node whose removal minimizes the maximum size forest from an N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int mini = 105 , ans , n ; vector < vector < int > > g ( 100 ) ; int size [ 100 ] ; void create_graph ( ) { g [ 1 ] . push_back ( 2 ) ; g [ 2 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 3 ) ; g [ 3 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 4 ) ; g [ 4 ] . push_back ( 1 ) ; g [ 2 ] . push_back ( 5 ) ; g [ 5 ] . push_back ( 2 ) ; g [ 2 ] . push_back ( 6 ) ; g [ 6 ] . push_back ( 2 ) ; } 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 = max ( mx , size [ y ] ) ; } mx = max ( mx , n - size [ node ] ) ; if ( mx < mini ) { mini = mx ; ans = node ; } } int main ( ) { n = 6 ; create_graph ( ) ; dfs ( 1 , -1 ) ; cout << ans << " STRNEWLINE " ; return 0 ; }