Given an n-ary tree T, the task is to find a node whose removal minimizes the maximum size of all forests(connected components) generated.
Examples:
Input:
1
/ | \
2 3 4
/ \
5 6
Output: 1
Explanation:
There are six nodes which can be removed to form forests:
Remove(1): Largest Forest size is 3
Remove(2): Largest Forest size is 3
Remove(3): Largest Forest size is 5
Remove(4): Largest Forest size is 5
Remove(5): Largest Forest size is 5
Remove(6): Largest Forest size is 5
Therefore, removing either node 1 or 2 minimizes the maximum forest size to 3.Input:
1
/ \
2 3
Output: 1
Explanation:
There are three nodes which can be removed to form forests:
Remove(1): Largest Forest size is 1
Remove(2): Largest Forest size is 1
Remove(3): Largest Forest size is 1
Therefore, removing either node 1 or 2 or 3 minimizes the maximum forest size to 1.
Approach: The idea is to traverse the tree using Depth First Search Traversal and for every node of the tree, count the number of nodes in its subtree. Removing any node from the given tree leads to two different types of forests:
- Connected components formed by the subtrees including its left and right child.
- Connected components formed by the subtree including its parent node
Therefore, follow the steps below to solve the problem:
- Traverse the tree using DFS.
- For every node, compute the number of nodes in its child subtrees recursively. Calculate the number of nodes in the connected component involving its parent by calculating the difference of the total number of nodes in the given tree and the sum of nodes in its child subtrees.
- Keep updating minimum of the maximum size of connected components obtained for any node.
- Finally, print the node corresponding to which the minimum of the maximum size of connected components is obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;int mini = 105, ans, n;vector<vector<int> > g(100);int size[100];// Function to create the graphvoid 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);}// Function to traverse the graph// and find the minimum of maximum// size forest after removing a nodevoid dfs(int node, int parent){ size[node] = 1; int mx = 0; // Traversing every child subtree // except the parent node for (int y : g[node]) { if (y == parent) continue; // Traverse all subtrees dfs(y, node); size[node] += size[y]; // Update the maximum // size of forests mx = max(mx, size[y]); } // Update the minimum of maximum // size of forests obtained mx = max(mx, n - size[node]); // Condition to find the minimum // of maximum size forest if (mx < mini) { mini = mx; // Update and store the // corresponding node ans = node; }}// Driver Codeint main(){ n = 6; create_graph(); dfs(1, -1); cout << ans << "\n"; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static int mini = 105, ans, n;static Vector<Integer> []g = new Vector[100];static int []size = new int[100];// Function to create the graphstatic 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);}// Function to traverse the graph// and find the minimum of maximum// size forest after removing a nodestatic void dfs(int node, int parent){ size[node] = 1; int mx = 0; // Traversing every child subtree // except the parent node for (int y : g[node]) { if (y == parent) continue; // Traverse all subtrees dfs(y, node); size[node] += size[y]; // Update the maximum // size of forests mx = Math.max(mx, size[y]); } // Update the minimum of maximum // size of forests obtained mx = Math.max(mx, n - size[node]); // Condition to find the minimum // of maximum size forest if (mx < mini) { mini = mx; // Update and store the // corresponding node ans = node; }}// Driver Codepublic 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 + "\n");}}// This code is contributed by Princi Singh |
Python3
# Python3 program to implement# the above approachmini = 105;ans = 0;n = 0;g = [];size = [0] * 100;# Function to create the graphdef create_graph(): g[1].append(2); g[2].append(1); g[1].append(3); g[3].append(1); g[1].append(4); g[4].append(1); g[2].append(5); g[5].append(2); g[2].append(6); g[6].append(2);# Function to traverse the graph# and find the minimum of maximum# size forest after removing a Nodedef dfs(Node, parent): size[Node] = 1; mx = 0; global mini global ans # Traversing every child subtree # except the parent Node for y in g[Node]: if (y == parent): continue; # Traverse all subtrees dfs(y, Node); size[Node] += size[y]; # Update the maximum # size of forests mx = max(mx, size[y]); # Update the minimum of maximum # size of forests obtained mx = max(mx, n - size[Node]); # Condition to find the minimum # of maximum size forest if (mx < mini): mini = mx; # Update and store the # corresponding Node ans = Node;# Driver Codeif __name__ == '__main__': n = 6; for i in range(100): g.append([]) create_graph(); dfs(1, -1); print(ans);# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{static int mini = 105, ans, n;static List<int> []g = new List<int>[100];static int []size = new int[100];// Function to create the graphstatic 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);}// Function to traverse the graph// and find the minimum of maximum// size forest after removing a nodestatic void dfs(int node, int parent){ size[node] = 1; int mx = 0; // Traversing every child subtree // except the parent node foreach (int y in g[node]) { if (y == parent) continue; // Traverse all subtrees dfs(y, node); size[node] += size[y]; // Update the maximum // size of forests mx = Math.Max(mx, size[y]); } // Update the minimum of maximum // size of forests obtained mx = Math.Max(mx, n - size[node]); // Condition to find the minimum // of maximum size forest if (mx < mini) { mini = mx; // Update and store the // corresponding node ans = node; }}// Driver Codepublic static void Main(String[] args){ n = 6; for (int i = 0; i < g.Length; i++) g[i] = new List<int>(); create_graph(); dfs(1, -1); Console.Write(ans + "\n");}}// This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program to implement// the above approachvar mini = 105, ans, n;var g = Array.from(Array(100), ()=> new Array());var size = Array(100).fill(0);// Function to create the graphfunction 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 to traverse the graph// and find the minimum of Math.maximum// size forest after removing a nodefunction dfs(node, parent){ size[node] = 1; var mx = 0; // Traversing every child subtree // except the parent node g[node].forEach(y => { if (y != parent) { // Traverse all subtrees dfs(y, node); size[node] += size[y]; // Update the Math.maximum // size of forests mx = Math.max(mx, size[y]); } }); // Update the minimum of Math.maximum // size of forests obtained mx = Math.max(mx, n - size[node]); // Condition to find the minimum // of Math.maximum size forest if (mx < mini) { mini = mx; // Update and store the // corresponding node ans = node; }}// Driver Coden = 6;create_graph();dfs(1, -1);document.write( ans );</script> |
Output
2
Time Complexity: O(N), where N is the number of nodes.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
