Dado un árbol con N Nodes, numerados de 0 a N – 1, la tarea es encontrar el número mínimo de eliminación de bordes, de modo que el árbol se convierta en un bosque donde cada árbol en el bosque puede tener un tamaño menor que igual a ⌊N/2⌋.
Ejemplos:
Entrada : N = 3, bordes = [[0, 1], [0, 2]]
0
/ \
1 2
Salida : 2
Explicación: El tamaño máximo de cada árbol después de eliminar los bordes puede ser 1.
Entonces, cada Node tiene que ser separados unos de otros.
Entonces, elimine todos los 2 bordes presentes en el árbol.
Por lo tanto, la respuesta será 2.Entrada : N = 7, bordes = [[0, 1], [1, 2], [1, 3], [0, 4], [4, 5], [4, 6]]
0
/ \
1 4
/ \ / \
2 3 5 6
Salida : 2
Explicación : elimine los bordes (0 – 1) y (0 – 4) para satisfacer la condición. Por lo tanto, la respuesta será 2.
Enfoque: La idea para resolver el problema es usar la búsqueda en profundidad primero .
Siga los pasos para resolver el problema dado:
- Cree el gráfico a partir de la entrada dada.
- Calcule los centroides usando la función dfs .
- Si el árbol tiene dos centroides, entonces la respuesta será 1.
- De lo contrario, declare un vector subtreeSize, que calculará el tamaño del subárbol de todos los hijos del centroide.
- Calcule los tamaños de los subárboles usando la función dfs2 .
- Declare dos variables, ans y sum , para almacenar la respuesta y la cantidad de Nodes eliminados debido a la eliminación de los bordes .
- Ordene el subtreeSize en orden descendente.
- Iterar sobre el vector subtreeSize.
- Agregue el valor actual a la suma y aumente el ans en 1.
- Si los Nodes restantes son menores o iguales a N/ 2
- Rompe el bucle.
- Finalmente, devuelva el ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// Centroids of the tree.
void dfs(int n, int par,
vector<int>* ar,
vector<int>& size,
int& cent1, int& cent2,
int& some, int tot)
{
size[n] = 1;
int mx = 0;
// Iterate through the children
// of the current node and
// store the maximum of the subtree size
// among the children in the mx variable.
for (int child : ar[n]) {
if (child != par) {
dfs(child, n, ar, size,
cent1, cent2, some, tot);
size[n] += size[child];
mx = max(mx, size[child]);
}
}
mx = max(mx, tot - size[n]);
// If mx is smaller than the maximum
// subtree size till now,
// update that and centroids accordingly.
if (mx < some) {
some = mx;
cent1 = n;
cent2 = -1;
}
else if (mx == some) {
cent2 = n;
}
}
// Function to calculate the subtree
// size of the given node.
void dfs2(int n, int par,
vector<int>* ar, int& val)
{
val++;
for (int child : ar[n]) {
if (child != par) {
dfs2(child, n, ar, val);
}
}
}
int minimumEdges(int n,
vector<vector<int> >& edges)
{
vector<int> ar[n];
vector<int> size(n, 0);
// Create the graph
// From the given input.
for (int i = 0; i < n - 1; i++) {
ar[edges[i][0]]
.push_back(edges[i][1]);
ar[edges[i][1]]
.push_back(edges[i][0]);
}
int cent1 = -1, cent2 = -1, some = 1000000;
// Calculate the centroids
// Using the dfs function.
dfs(0, -1, ar, size,
cent1, cent2, some, n);
// If the tree has two centroids,
// Then the answer will be 1.
if (cent2 != -1) {
return 1;
}
// Declare a vector subtreeSize,
// Which will calculate the
// Subtree size of all the children
// Of the centroid.
vector<int> subtree_size;
// Calculate the subtree sizes
// Using the dfs2 function.
for (int x : ar[cent1]) {
int val = 0;
dfs2(x, cent1, ar, val);
subtree_size.push_back(val);
}
// Declare two variables, ans and sum,
// To store the answer
// And the number of nodes removed
// Due to the removal of edges.
int sum = 0;
int ans = 0;
// Sort the subtreeSize
// In descending order.
sort(subtree_size.rbegin(),
subtree_size.rend());
// Iterate over the “subtreeSize” vector.
for (int x : subtree_size) {
// Add the current value to the sum
// And increase the ans by 1.
sum += x;
ans++;
// If the remaining nodes are
// Less than or equal to N / 2,
// Break the loop.
if (n - sum <= n / 2) {
break;
}
}
// Finally, return the ans.
return ans;
}
// Driver code
int main()
{
int N = 3;
vector<vector<int> > edges
= { { 0, 1 }, { 0, 2 } };
cout << minimumEdges(N, edges) << "\n";
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
static int cent1,cent2;
static int[] size;
static int val;
// Function to calculate the
// Centroids of the tree.
static void dfs(int n, int par,
ArrayList <ArrayList <Integer>> ar,
int some, int tot)
{
size[n] = 1;
int mx = 0;
// Iterate through the children
// of the current node and
// store the maximum of the subtree size
// among the children in the mx variable.
for (int child : ar.get(n)) {
if (child != par) {
dfs(child, n, ar, some, tot);
size[n] += size[child];
mx = Math.max(mx, size[child]);
}
}
mx = Math.max(mx, tot - size[n]);
// If mx is smaller than the maximum
// subtree size till now,
// update that and centroids accordingly.
if (mx < some) {
some = mx;
cent1 = n;
cent2 = -1;
}
else if (mx == some) {
cent2 = n;
}
}
// Function to calculate the subtree
// size of the given node.
static void dfs2(int n, int par,
ArrayList <ArrayList<Integer>> ar)
{
val++;
for (int child : ar.get(n)) {
if (child != par) {
dfs2(child, n, ar);
}
}
}
static int minimumEdges(int n,int[][] edges)
{
ArrayList <ArrayList <Integer>> ar
= new ArrayList <ArrayList<Integer>> (n);
for(int i=0; i<n; i++){
ar.add( new ArrayList <Integer> () );
}
size = new int[n];
Arrays.fill(size, 0);
// Create the graph
// From the given input.
for (int i = 0; i < n - 1; i++) {
ar.get(edges[i][0])
.add(edges[i][1]);
ar.get(edges[i][1])
.add(edges[i][0]);
}
cent1 = -1;
cent2 = -1;
int some = 1000000;
// Calculate the centroids
// Using the dfs function.
dfs(0, -1, ar, some, n);
// If the tree has two centroids,
// Then the answer will be 1.
if (cent2 != -1) {
return 1;
}
// Declare a vector subtreeSize,
// Which will calculate the
// Subtree size of all the children
// Of the centroid.
ArrayList <Integer> subtree_size = new ArrayList <Integer> ();
// Calculate the subtree sizes
// Using the dfs2 function.
for (int x : ar.get(cent1) ) {
val = 0;
dfs2(x, cent1, ar);
subtree_size.add(val);
}
// Declare two variables, ans and sum,
// To store the answer
// And the number of nodes removed
// Due to the removal of edges.
int sum = 0;
int ans = 0;
// Sort the subtreeSize
// In descending order.
Collections.sort(subtree_size);
// Iterate over the “subtreeSize” vector.
for (int x : subtree_size) {
// Add the current value to the sum
// And increase the ans by 1.
sum += x;
ans++;
// If the remaining nodes are
// Less than or equal to N / 2,
// Break the loop.
if (n - sum <= n / 2) {
break;
}
}
// Finally, return the ans.
return ans;
}
// Driver Code
public static void main(String args[])
{
int N = 3;
int[][] edges
= { { 0, 1 }, { 0, 2 } };
// Function call
System.out.println( minimumEdges(N, edges) );
}
}
// This code has been contributed by Sachin Sahara (sachin801)
Python3
## Function to calculate the ## Centroids of the tree. def dfs(n, par, ar, size, lis, tot) : size[n] = 1 mx = 0 ## Iterate through the children ## of the current node and ## store the maximum of the subtree size ## among the children in the mx variable. for child in ar[n]: if (child != par): dfs(child, n, ar, size, lis, tot) size[n] += size[child] mx = max(mx, size[child]) mx = max(mx, tot - size[n]); ## If mx is smaller than the maximum ## subtree size till now, ## update that and centroids accordingly. if (mx < lis[2]): lis[2] = mx; lis[0] = n; lis[1] = -1; elif (mx == lis[2]): lis[1] = n; ## Function to calculate the subtree ## size of the given node. def dfs2(n, par, ar, val): val = 1 for child in ar[n]: if (child != par): val += dfs2(child, n, ar, val) return val def minimumEdges(n, edges): ar = [] size = [] for i in range(n): ar.append(list()) size.append(0) ## Create the graph ## From the given input. for i in range(n-1): ar[edges[i][0]].append(edges[i][1]) ar[edges[i][1]].append(edges[i][0]) cent1 = -1 cent2 = -1 some = 1000000 lis = [-1, -1, 1000000] ## Calculate the centroids ## Using the dfs function. dfs(0, -1, ar, size, lis, n); cent1 = lis[0] cent2 = lis[1] some = lis[2] ## If the tree has two centroids, ## Then the answer will be 1. if (cent2 != -1): return 1 ## Declare a vector subtreeSize, ## Which will calculate the ## Subtree size of all the children ## Of the centroid. subtree_size = [] ## Calculate the subtree sizes ## Using the dfs2 function. for x in ar[cent1]: val = 0 val = dfs2(x, cent1, ar, val) subtree_size.append(val) ## Declare two variables, ans and sum, ## To store the answer ## And the number of nodes removed ## Due to the removal of edges. sum = 0 ans = 0 ## Sort the subtreeSize ## In descending order. subtree_size.sort() ## Iterate over the “subtreeSize” vector. for x in subtree_size: ## Add the current value to the sum ## And increase the ans by 1. sum += x ans += 1 ## If the remaining nodes are ## Less than or equal to N / 2, ## Break the loop. if (n - sum <= n / 2): break; return ans # Driver Code if __name__ == "__main__": N = 3 edges = list((list((0, 1)), list((0, 2)))) print(minimumEdges(N, edges)) # This code is contributed by subhamgoyal2014.
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
public class GFG {
static int cent1,cent2;
static int[] size;
static int val;
// Function to calculate the
// Centroids of the tree.
static void dfs(int n, int par,
List <List <int>> ar,
int some, int tot)
{
size[n] = 1;
int mx = 0;
// Iterate through the children
// of the current node and
// store the maximum of the subtree size
// among the children in the mx variable.
foreach (int child in ar[n]) {
if (child != par) {
dfs(child, n, ar, some, tot);
size[n] += size[child];
mx = Math.Max(mx, size[child]);
}
}
mx = Math.Max(mx, tot - size[n]);
// If mx is smaller than the maximum
// subtree size till now,
// update that and centroids accordingly.
if (mx < some) {
some = mx;
cent1 = n;
cent2 = -1;
}
else if (mx == some) {
cent2 = n;
}
}
// Function to calculate the subtree
// size of the given node.
static void dfs2(int n, int par,
List <List<int>> ar)
{
val++;
foreach (int child in ar[n]) {
if (child != par) {
dfs2(child, n, ar);
}
}
}
static int minimumEdges(int n,int[,] edges)
{
List <List <int>> ar
= new List <List<int>> (n);
for(int i=0; i<n; i++){
ar.Add( new List <int> () );
}
size = new int[n];
// Arrays.fill(size, 0);
// Create the graph
// From the given input.
for (int i = 0; i < n - 1; i++) {
ar[edges[i,0]]
.Add(edges[i,1]);
ar[edges[i,1]]
.Add(edges[i,0]);
}
cent1 = -1;
cent2 = -1;
int some = 1000000;
// Calculate the centroids
// Using the dfs function.
dfs(0, -1, ar, some, n);
// If the tree has two centroids,
// Then the answer will be 1.
if (cent2 != -1) {
return 1;
}
// Declare a vector subtreeSize,
// Which will calculate the
// Subtree size of all the children
// Of the centroid.
List <int> subtree_size = new List <int> ();
// Calculate the subtree sizes
// Using the dfs2 function.
foreach (int x in ar[cent1] ) {
val = 0;
dfs2(x, cent1, ar);
subtree_size.Add(val);
}
// Declare two variables, ans and sum,
// To store the answer
// And the number of nodes removed
// Due to the removal of edges.
int sum = 0;
int ans = 0;
// Sort the subtreeSize
// In descending order.
subtree_size.Sort();
// Iterate over the “subtreeSize�? vector.
foreach (int x in subtree_size) {
// Add the current value to the sum
// And increase the ans by 1.
sum += x;
ans++;
// If the remaining nodes are
// Less than or equal to N / 2,
// Break the loop.
if (n - sum <= n / 2) {
break;
}
}
// Finally, return the ans.
return ans;
}
// Driver Code
public static void Main(String []args)
{
int N = 3;
int[,] edges
= { { 0, 1 }, { 0, 2 } };
// Function call
Console.WriteLine( minimumEdges(N, edges) );
}
}
// This code is contributed by shikhasingrajput
Producción
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)