Tiempo mínimo requerido para colorear todos los bordes de un árbol

Dada una array de pares Edges[][] , que representa los bordes que conectan los vértices en un árbol que consta de N Nodes, la tarea es encontrar el tiempo mínimo requerido para colorear todos los bordes de un árbol en función de la suposición de que colorear un borde requiere 1 unidad de tiempo 

Nota: Se pueden colorear varios bordes en un instante en particular, pero un Node puede ser parte de solo uno de los bordes coloreados en un día en particular. 

Ejemplos

Entrada: Bordes[][] = ((1, 2), (3, 4), (2, 3))

Salida: 2
Explicación: 
Paso 1: Colorea los bordes (1, 2) y (3, 4)
Paso 2: Colorea el borde (2, 3) 

Entrada: Bordes[][] = ((1, 2), (1, 3), (1, 4))

Salida : 3

Enfoque: este problema se puede resolver utilizando DFS (búsqueda primero en profundidad) . Siga los pasos a continuación para resolver el problema:

• Inicialice las variables globales, digamos ans como 0, para almacenar el tiempo mínimo requerido para colorear todos los bordes de un árbol.
• Inicialice una variable current_time como 0, para almacenar el tiempo requerido para colorear el borde actual.
• Iterar sobre los elementos secundarios del Node actual y realizar los siguientes pasos:
  • Si no se visita el borde actual, es decir, el Node actual no es igual al Node principal:
    • Aumentar current_time en 1 .
    • Compruebe si el borde principal se ha coloreado al mismo tiempo o no. Si se determina que es cierto, aumente current_time en 1 , ya que un Node no puede ser parte de más de un borde que se está coloreando al mismo tiempo.
    • Actualice ans como máximo de ans y hora_actual. 
    • Llame a la función recursiva minTimeToColor para los elementos secundarios del Node actual.
• Después del final de esta función, imprima ans .

A continuación se muestra el código para el enfoque anterior.

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the required answer
int ans = 0;
 
// Stores the graph
vector<int> edges[100000];
 
// Function to add edges
void Add_edge(int u, int v)
{
    edges[u].push_back(v);
    edges[v].push_back(u);
}
 
// Function to calculate the minimum time
// required to color all the edges of a tree
void minTimeToColor(int node, int parent,
                    int arrival_time)
{
    // Starting from time = 0,
    // for all the child edges
    int current_time = 0;
 
    for (auto x : edges[node]) {
 
        // If the edge is not visited yet.
        if (x != parent) {
 
            // Time of coloring of
            // the current edge
            ++current_time;
 
            // If the parent edge has
            // been colored at the same time
            if (current_time == arrival_time)
                ++current_time;
 
            // Update the maximum time
            ans = max(ans, current_time);
 
            // Recursively call the
            // function to its child node
            minTimeToColor(x, node, current_time);
        }
    }
}
 
// Driver Code
int main()
{
 
    pair<int, int> A[] = { { 1, 2 },
                           { 2, 3 },
                           { 3, 4 } };
 
    for (auto i : A) {
 
        Add_edge(i.first, i.second);
    }
 
    // Function call
    minTimeToColor(1, -1, 0);
 
    // Finally, print the answer
    cout << ans << "\n";
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Stores the required answer
static int ans = 0;
 
// Stores the graph
@SuppressWarnings("unchecked")
static Vector<Integer> edges[] = new Vector[100000];
 
// Function to add edges
static void Add_edge(int u, int v)
{
    edges[u].add(v);
    edges[v].add(u);
}
 
// Function to calculate the minimum time
// required to color all the edges of a tree
static void minTimeToColor(int node, int parent,
                           int arrival_time)
{
     
    // Starting from time = 0,
    // for all the child edges
    int current_time = 0;
 
    for(int x = 0; x < edges[node].size(); x++)
    {
         
        // If the edge is not visited yet.
        if (edges[node].get(x) != parent)
        {
             
            // Time of coloring of
            // the current edge
            ++current_time;
 
            // If the parent edge has
            // been colored at the same time
            if (current_time == arrival_time)
                ++current_time;
 
            // Update the maximum time
            ans = Math.max(ans, current_time);
 
            // Recursively call the
            // function to its child node
            minTimeToColor(edges[node].get(x), node,
                           current_time);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    for(int i = 0; i < edges.length; i++)
        edges[i] = new Vector<Integer>();
         
    int A[][] = { { 1, 2 },
                  { 2, 3 },
                  { 3, 4 } };
 
    for(int i = 0; i < 3; i++)
    {
        Add_edge(A[i][0], A[i][1]);
    }
     
    // Function call
    minTimeToColor(1, -1, 0);
 
    // Finally, print the answer
    System.out.print(ans + "\n");
}
}
 
// This code is contributed by umadevi9616

# Python3 program for the above approach
 
# Stores the required answer
ans = 0
 
# Stores the graph
edges = [[] for i in range(100000)]
 
# Function to add edges
def Add_edge(u, v):
     
    global edges
    edges[u].append(v)
    edges[v].append(u)
 
# Function to calculate the minimum time
# required to color all the edges of a tree
def minTimeToColor(node, parent, arrival_time):
     
    global ans
     
    # Starting from time = 0,
    # for all the child edges
    current_time = 0
 
    for x in edges[node]:
 
        # If the edge is not visited yet.
        if (x != parent):
 
            # Time of coloring of
            # the current edge
            current_time += 1
 
            # If the parent edge has
            # been colored at the same time
            if (current_time == arrival_time):
                current_time += 1
 
            # Update the maximum time
            ans = max(ans, current_time)
 
            # Recursively call the
            # function to its child node
            minTimeToColor(x, node, current_time)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ [ 1, 2 ],
          [ 2, 3 ],
          [ 3, 4 ] ]
 
    for i in A:
        Add_edge(i[0], i[1])
 
    # Function call
    minTimeToColor(1, -1, 0)
 
    # Finally, print the answer
    print(ans)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Stores the required answer
    static int ans = 0;
      
    // Stores the graph
    static List<List<int>> edges = new List<List<int>>();
      
    // Function to add edges
    static void Add_edge(int u, int v)
    {
        edges[u].Add(v);
        edges[v].Add(u);
    }
     
    // Function to calculate the minimum time
    // required to color all the edges of a tree
    static void minTimeToColor(int node, int parent,
                        int arrival_time)
    {
        // Starting from time = 0,
        // for all the child edges
        int current_time = 0;
      
        for(int x = 0; x < edges[node].Count; x++) {
      
            // If the edge is not visited yet.
            if (edges[node][x] != parent) {
      
                // Time of coloring of
                // the current edge
                ++current_time;
      
                // If the parent edge has
                // been colored at the same time
                if (current_time == arrival_time)
                    ++current_time;
      
                // Update the maximum time
                ans = Math.Max(ans, current_time);
      
                // Recursively call the
                // function to its child node
                minTimeToColor(edges[node][x], node, current_time);
            }
        }
    }
 
  // Driver code
  static void Main() {
     
    for(int i = 0; i < 100000; i++)
    {
        edges.Add(new List<int>());
    }
     
    int[,] A = { { 1, 2 }, { 2, 3 }, { 3, 4 } };
  
    for(int i = 0; i < 3; i++)
    {
        Add_edge(A[i,0], A[i,1]);
    }
  
    // Function call
    minTimeToColor(1, -1, 0);
  
    // Finally, print the answer
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// JavaScript program for the above approach
 
// Stores the required answer
let ans = 0;
 
// Stores the graph
let edges=new Array(100000);
for(let i=0;i<100000;i++)
    edges[i]=[];
 
// Function to add edges
function Add_edge(u,v)
{
    edges[u].push(v);
    edges[v].push(u);
}
 
// Function to calculate the minimum time
// required to color all the edges of a tree   
function minTimeToColor(node,parent,arrival_time)
{
    // Starting from time = 0,
    // for all the child edges
    let current_time = 0;
  
    for (let x=0;x<edges[node].length;x++) {
  
        // If the edge is not visited yet.
        if (edges[node][x] != parent) {
  
            // Time of coloring of
            // the current edge
            ++current_time;
  
            // If the parent edge has
            // been colored at the same time
            if (current_time == arrival_time)
                ++current_time;
  
            // Update the maximum time
            ans = Math.max(ans, current_time);
  
            // Recursively call the
            // function to its child node
            minTimeToColor(edges[node][x], node, current_time);
        }
    }
}
 
// Driver Code
let A=[[ 1, 2 ],[ 2, 3 ],[ 3, 4 ] ];
for(let i=0;i<A.length;i++)
{
    Add_edge(A[i][0],A[i][1]);
}
// Function call
minTimeToColor(1, -1, 0);
 
// Finally, print the answer
document.write(ans);
 
// This code is contributed by patel2127
 
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)