Minimum number of Nodes to be removed such that no subtree has more than K nodes | C # program for the above approach ; Variables used to store data globally ; Adjacency list representation of tree ; Function to perform DFS Traversal ; Mark the node as true ; Traverse adjacency list of child node ; If already visited then omit the node ; Add number of nodes in subtree ; Increment the count ; Return the nodes ; Function to add edges in graph ; Function that finds the number of nodes to be removed such that every subtree has size at most K ; Function Call to find the number of nodes to remove ; Print Removed Nodes ; Driver Code ; Creating list for all nodes ; Insert of nodes in graph ; Required subtree size ; Function Call
using System ; using System . Collections . Generic ; class GFG { static readonly int N = 20 ; static bool [ ] visited = new bool [ N ] ; static int K ; static int removals = 0 ; static List < int > removed_nodes = new List < int > ( ) ; static List < List < int > > adj = new List < List < int > > ( ) ; static int dfs ( int s ) { visited [ s ] = true ; int nodes = 1 ; foreach ( int child in adj [ s ] ) { if ( visited [ child ] ) continue ; nodes += dfs ( child ) ; } if ( nodes > K ) { removals ++ ; removed_nodes . Add ( s ) ; nodes = 0 ; } return nodes ; } static void addEdge ( int a , int b ) { adj [ a ] . Add ( b ) ; adj [ b ] . Add ( a ) ; } public static void findRemovedNodes ( int K ) { dfs ( 1 ) ; Console . WriteLine ( " Number ▁ of ▁ nodes " + " ▁ removed : ▁ " + removals ) ; Console . Write ( " Removed ▁ Nodes : ▁ " ) ; foreach ( int node in removed_nodes ) Console . Write ( node + " ▁ " ) ; } public static void Main ( String [ ] args ) { for ( int i = 0 ; i < N ; i ++ ) adj . Add ( new List < int > ( ) ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 3 , 6 ) ; K = 3 ; findRemovedNodes ( K ) ; } }