Convert a tree to forest of even nodes | C # program to find maximum number to be removed to convert a tree into forest containing trees of even number of nodes ; Return the number of nodes of subtree having node as a root . ; Mark node as visited . ; Traverse the adjacency list to find non - visited node . ; Finding number of nodes of the subtree of a subtree . ; If nodes are even , increment number of edges to removed . Else leave the node as child of subtree . ; Return the maximum number of edge to remove to make forest . ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int N = 12 , ans ; static List < List < int > > tree = new List < List < int > > ( ) ; static int dfs ( int [ ] visit , int node ) { int num = 0 , temp = 0 ; visit [ node ] = 1 ; for ( int i = 0 ; i < tree [ node ] . Count ; i ++ ) { if ( visit [ tree [ node ] [ i ] ] == 0 ) { temp = dfs ( visit , tree [ node ] [ i ] ) ; if ( temp % 2 != 0 ) num += temp ; else ans ++ ; } } return num + 1 ; } static int minEdge ( int n ) { int [ ] visit = new int [ n + 2 ] ; ans = 0 ; dfs ( visit , 1 ) ; return ans ; } public static void Main ( String [ ] args ) { int n = 10 ; for ( int i = 0 ; i < n + 2 ; i ++ ) tree . Add ( new List < int > ( ) ) ; tree [ 1 ] . Add ( 3 ) ; tree [ 3 ] . Add ( 1 ) ; tree [ 1 ] . Add ( 6 ) ; tree [ 6 ] . Add ( 1 ) ; tree [ 1 ] . Add ( 2 ) ; tree [ 2 ] . Add ( 1 ) ; tree [ 3 ] . Add ( 4 ) ; tree [ 4 ] . Add ( 3 ) ; tree [ 6 ] . Add ( 8 ) ; tree [ 8 ] . Add ( 6 ) ; tree [ 2 ] . Add ( 7 ) ; tree [ 7 ] . Add ( 2 ) ; tree [ 2 ] . Add ( 5 ) ; tree [ 5 ] . Add ( 2 ) ; tree [ 4 ] . Add ( 9 ) ; tree [ 9 ] . Add ( 4 ) ; tree [ 4 ] . Add ( 10 ) ; tree [ 10 ] . Add ( 4 ) ; Console . WriteLine ( minEdge ( n ) ) ; } }