Node cuya eliminación minimiza el tamaño máximo del bosque de un árbol N-ario

Dado un árbol n-ario T , la tarea es encontrar un Node cuya eliminación minimice el tamaño máximo de todos los bosques ( componentes conectados ) generados.

Ejemplos:

Entrada: 
                     1
                  / | \
                2 3 4
              / \
            5 6
Salida: 1
Explicación:
Hay seis Nodes que se pueden quitar para formar bosques:
Remove(1): El tamaño más grande del bosque es 3
Remove(2): El tamaño más grande del bosque es 3
Remove(3): El tamaño del bosque más grande es 5
Remove(4): El tamaño del bosque más grande es 5
Remove(5): El tamaño del bosque más grande es 5
Remove(6): El tamaño del bosque más grande es 5
Por lo tanto, eliminar el Node 1 o el 2 minimiza el tamaño máximo del bosque a 3 .

Entrada: 
                 1
               / \
             2 3
Salida: 1
Explicación:
Hay tres Nodes que se pueden eliminar para formar bosques:
Eliminar (1): el tamaño más grande del bosque es 1
Eliminar (2): el tamaño más grande del bosque es 1
Eliminar (3): el más grande El tamaño del bosque es 1.
Por lo tanto, eliminar el Node 1, 2 o 3 minimiza el tamaño máximo del bosque a 1.

Enfoque : la idea es recorrer el árbol utilizando la exploración transversal de búsqueda en profundidad y, para cada Node del árbol, contar el número de Nodes en su subárbol. Eliminar cualquier Node del árbol dado conduce a dos tipos diferentes de bosques:

• Componentes conectados formados por los subárboles, incluido su hijo izquierdo y derecho.
• Componentes conectados formados por el subárbol, incluido su Node principal

Por lo tanto, siga los pasos a continuación para resolver el problema:  

• Atraviesa el árbol usando DFS .
• Para cada Node, calcule el número de Nodes en sus subárboles secundarios de forma recursiva . Calcule la cantidad de Nodes en el componente conectado que involucra a su padre calculando la diferencia de la cantidad total de Nodes en el árbol dado y la suma de Nodes en sus subárboles secundarios.
• Mantenga la actualización mínima del tamaño máximo de los componentes conectados obtenidos para cualquier Node.
• Finalmente, imprima el Node correspondiente al que se obtiene el tamaño mínimo o máximo de los componentes conectados.

A continuación se muestra la implementación del enfoque anterior:

// 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 graph
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);
}
 
// Function to traverse the graph
// and find the minimum of maximum
// size forest after removing a node
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 = 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 Code
int main()
{
    n = 6;
 
    create_graph();
 
    dfs(1, -1);
 
    cout << ans << "\n";
 
    return 0;
}

// Java program to implement
// the above approach
import 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 graph
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);
}
 
// Function to traverse the graph
// and find the minimum of maximum
// size forest after removing a node
static 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 Code
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 + "\n");
}
}
 
// This code is contributed by Princi Singh

# Python3 program to implement
# the above approach
mini = 105;
ans = 0;
n = 0;
g = [];
size = [0] * 100;
 
# Function to create the graph
def 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 Node
def 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 Code
if __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# program to implement
// the above approach
using 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 graph
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);
}
 
// Function to traverse the graph
// and find the minimum of maximum
// size forest after removing a node
static 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 Code
public 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

<script>
  
// JavaScript program to implement
// the above approach
 
var mini = 105, ans, n;
var g = Array.from(Array(100), ()=> new Array());
var size = Array(100).fill(0);
 
// Function to create the graph
function 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 node
function 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 Code
 
n = 6;
create_graph();
dfs(1, -1);
document.write( ans );
 
</script>

2

Complejidad temporal: O(N), donde N es el número de Nodes.
Espacio Auxiliar: O(N)