Eliminación máxima de bordes del árbol para hacer un bosque parejo

Dado un árbol no dirigido que tiene un número par de vértices, debemos eliminar el número máximo de aristas de este árbol de modo que cada componente conectado del bosque resultante tenga un número par de vértices. 

Ejemplos: 

In above shown tree, we can remove at max 2 
edges 0-2 and 0-4 shown in red such that each
connected component will have even number of
vertices.

Como necesitamos componentes conectados que tengan un número par de vértices, cuando obtengamos un componente podemos eliminar el borde que lo conecta con el árbol restante y nos quedará un árbol con un número par de vértices, que será el mismo problema pero de tamaño más pequeño, tenemos que repetir este algoritmo hasta que el árbol restante no se pueda descomponer más de la manera anterior. 

Atravesaremos el árbol usando DFS que devolverá el número de vértices en el componente del cual el Node actual es la raíz. Si un Node obtiene un número par de vértices de uno de sus hijos, se eliminará el borde de ese Node a su hijo y el resultado aumentará en uno y si el número devuelto es impar, lo agregaremos al número de vértices. que tendrá el componente si el Node actual es la raíz del mismo.

1) Do DFS from any starting node as tree
is connected.

2) Initialize count of nodes in subtree rooted
under current node as 0.

3) Do following recursively for every subtree
of current node.
    a) If size of current subtree is even,
       increment result by 1 as we can 
       disconnect the subtree.
    b) Else add count of nodes in current 
       subtree to current count.

Consulte el código a continuación para una mejor comprensión, 

/* Program to get maximum number of edges which
   can be removed such that each connected component
   of this tree will have an even number of vertices */
#include <bits/stdc++.h>
using namespace std;
 
// Utility method to do DFS of the graph and count edge
// deletion for even forest
int dfs(vector<int> g[], int u, bool visit[], int& res)
{
    visit[u] = true;
    int currComponentNode = 0;
 
    //  iterate over all neighbor of node u
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if (!visit[v])
        {
            // Count the number of nodes in a subtree
            int subtreeNodeCount = dfs(g, v, visit, res);
 
            // if returned node count is even, disconnect
            // the subtree and increase result by one.
            if (subtreeNodeCount % 2 == 0)
                res++;
 
            //  else add subtree nodes in current component
            else
                currComponentNode += subtreeNodeCount;
        }
    }
 
    // number of nodes in current component and one for
    // current node
    return (currComponentNode + 1);
}
 
/*  method returns max edge that we can remove, after which
    each  connected component will have even number of
    vertices */
int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N)
{
    // Create a visited array for DFS and make all nodes
    // unvisited in starting
    bool visit[N + 1];
    for (int i = 0; i <= N; i++)
        visit[i] = false;
 
    int res = 0; // Passed as reference
 
    //  calling the dfs from node-0
    dfs(g, 0, visit, res);
 
    return res;
}
 
// Utility function to add an undirected edge (u,v)
void addEdge(vector<int> g[], int u, int v)
{
    g[u].push_back(v);
    g[v].push_back(u);
}
 
//  Driver code to test above methods
int main()
{
    int edges[][2] = {{0, 2}, {0, 1}, {0, 4},
                      {2, 3}, {4, 5}, {5, 6},
                      {5, 7}};
    int N = sizeof(edges)/sizeof(edges[0]);
    vector<int> g[N + 1];
    for (int i = 0; i < N; i++)
         addEdge(g, edges[i][0], edges[i][1]);
 
    cout << maxEdgeRemovalToMakeForestEven(g, N);
    return 0;
}

/* Program to get maximum number of edges which
can be removed such that each connected component
of this tree will have an even number of vertices */
import java.util.*;
class GFG
{
     
// graph
static Vector<Vector<Integer>> g = new Vector<Vector<Integer>>();
 
static int res;
 
// Utility method to do DFS of the graph and count edge
// deletion for even forest
static int dfs( int u, boolean visit[])
{
    visit[u] = true;
    int currComponentNode = 0;
 
    // iterate over all neighbor of node u
    for (int i = 0; i < g.get(u).size(); i++)
    {
        int v = g.get(u).get(i);
        if (!visit[v])
        {
            // Count the number of nodes in a subtree
            int subtreeNodeCount = dfs(v, visit);
 
            // if returned node count is even, disconnect
            // the subtree and increase result by one.
            if (subtreeNodeCount % 2 == 0)
                res++;
 
            // else add subtree nodes in current component
            else
                currComponentNode += subtreeNodeCount;
        }
    }
 
    // number of nodes in current component and one for
    // current node
    return (currComponentNode + 1);
}
 
/* method returns max edge that we can remove, after which
    each connected component will have even number of
    vertices */
static int maxEdgeRemovalToMakeForestEven( int N)
{
    // Create a visited array for DFS and make all nodes
    // unvisited in starting
    boolean visit[]=new boolean[N + 1];
    for (int i = 0; i <= N; i++)
        visit[i] = false;
 
    res = 0; // Passed as reference
 
    // calling the dfs from node-0
    dfs(0, visit);
 
    return res;
}
 
// Utility function to add an undirected edge (u,v)
static void addEdge( int u, int v)
{
    g.get(u).add(v);
    g.get(v).add(u);
}
 
// Driver code to test above methods
public static void main(String args[])
{
    int edges[][] = {{0, 2}, {0, 1}, {0, 4},
                    {2, 3}, {4, 5}, {5, 6},
                    {5, 7}};
    int N = edges.length;
     
    for (int i = 0; i < N+1; i++)
    g.add(new Vector<Integer>());
     
    for (int i = 0; i < N; i++)
        addEdge( edges[i][0], edges[i][1]);
         
 
    System.out.println(maxEdgeRemovalToMakeForestEven( N));
}
}
 
// This code is contributed by Arnab Kundu

# Python3 program to get maximum number of
# edges which can be removed such that each
# connected component of this tree will
# have an even number of vertices
from typing import List
 
# Utility method to do DFS of the graph
# and count edge deletion for even forest
def dfs(u: int, visit: List[bool]) -> int:
     
    global res, g
 
    visit[u] = True
    currComponentNode = 0
 
    # Iterate over all neighbor of node u
    for i in range(len(g[u])):
        v = g[u][i]
         
        if (not visit[v]):
 
            # Count the number of nodes in a subtree
            subtreeNodeCount = dfs(v, visit)
 
            # If returned node count is even, disconnect
            # the subtree and increase result by one.
            if (subtreeNodeCount % 2 == 0):
                res += 1
 
            # Else add subtree nodes in
            # current component
            else:
                currComponentNode += subtreeNodeCount
 
    # Number of nodes in current component
    # and one for current node
    return (currComponentNode + 1)
 
# Method returns max edge that we can remove,
# after which each connected component will
# have even number of vertices
def maxEdgeRemovalToMakeForestEven(N: int) -> int:
     
    # Create a visited array for DFS and make
    # all nodes unvisited in starting
    visit = [False for _ in range(N + 1)]
 
    # Calling the dfs from node-0
    dfs(0, visit)
 
    return res
     
# Utility function to add an undirected edge (u,v)
def addEdge(u: int, v: int) -> None:
     
    global g
 
    g[u].append(v)
    g[v].append(u)
 
#  Driver code
if __name__ == "__main__":
 
    res = 0
    edges = [ [ 0, 2 ], [ 0, 1 ],
              [ 0, 4 ], [ 2, 3 ],
              [ 4, 5 ], [ 5, 6 ],
              [ 5, 7 ] ]
    N = len(edges)
    g = [[] for _ in range(N + 1)]
     
    for i in range(N):
        addEdge(edges[i][0], edges[i][1])
 
    print(maxEdgeRemovalToMakeForestEven(N))
 
# This code is contributed by sanjeev2552

/* C# Program to get maximum number of edges which
can be removed such that each connected component
of this tree will have an even number of vertices */
using System;
using System.Collections.Generic;
 
class GFG
{
     
// graph
static List<List<int>> g = new List<List<int>>();
 
static int res;
 
// Utility method to do DFS of the graph and
// count edge deletion for even forest
static int dfs( int u, bool []visit)
{
    visit[u] = true;
    int currComponentNode = 0;
 
    // iterate over all neighbor of node u
    for (int i = 0; i < g[u].Count; i++)
    {
        int v = g[u][i];
        if (!visit[v])
        {
            // Count the number of nodes in a subtree
            int subtreeNodeCount = dfs(v, visit);
 
            // if returned node count is even, disconnect
            // the subtree and increase result by one.
            if (subtreeNodeCount % 2 == 0)
                res++;
 
            // else add subtree nodes in current component
            else
                currComponentNode += subtreeNodeCount;
        }
    }
 
    // number of nodes in current component and one for
    // current node
    return (currComponentNode + 1);
}
 
/* method returns max edge that we can remove,
after which each connected component
will have even number of vertices */
static int maxEdgeRemovalToMakeForestEven( int N)
{
    // Create a visited array for DFS and
    // make all nodes unvisited in starting
    bool []visit = new bool[N + 1];
    for (int i = 0; i <= N; i++)
        visit[i] = false;
 
    res = 0; // Passed as reference
 
    // calling the dfs from node-0
    dfs(0, visit);
 
    return res;
}
 
// Utility function to add an undirected edge (u,v)
static void addEdge( int u, int v)
{
    g[u].Add(v);
    g[v].Add(u);
}
 
// Driver code
public static void Main(String []args)
{
    int [,]edges = {{0, 2}, {0, 1}, {0, 4},
                    {2, 3}, {4, 5}, {5, 6},
                    {5, 7}};
    int N = edges.GetLength(0);
     
    for (int i = 0; i < N + 1; i++)
    g.Add(new List<int>());
     
    for (int i = 0; i < N; i++)
        addEdge(edges[i, 0], edges[i, 1]);
 
    Console.WriteLine(maxEdgeRemovalToMakeForestEven(N));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
/* Program to get maximum number of edges which
can be removed such that each connected component
of this tree will have an even number of vertices */
 
// graph
let g = [];
let res;
 
// Utility method to do DFS of the graph and count edge
// deletion for even forest
function dfs(u,visit)
{
    visit[u] = true;
    let currComponentNode = 0;
  
    // iterate over all neighbor of node u
    for (let i = 0; i < g[u].length; i++)
    {
        let v = g[u][i];
        if (!visit[v])
        {
            // Count the number of nodes in a subtree
            let subtreeNodeCount = dfs(v, visit);
  
            // if returned node count is even, disconnect
            // the subtree and increase result by one.
            if (subtreeNodeCount % 2 == 0)
                res++;
  
            // else add subtree nodes in current component
            else
                currComponentNode += subtreeNodeCount;
        }
    }
  
    // number of nodes in current component and one for
    // current node
    return (currComponentNode + 1);
}
 
/* method returns max edge that we can remove, after which
    each connected component will have even number of
    vertices */
function maxEdgeRemovalToMakeForestEven(N)
{
    // Create a visited array for DFS and make all nodes
    // unvisited in starting
    let visit=new Array(N + 1);
    for (let i = 0; i <= N; i++)
        visit[i] = false;
  
    res = 0; // Passed as reference
  
    // calling the dfs from node-0
    dfs(0, visit);
  
    return res;
}
 
// Utility function to add an undirected edge (u,v)
function addEdge(u,v)
{
     g[u].push(v);
    g[v].push(u);
}
 
// Driver code to test above methods
let edges=[[0, 2], [0, 1], [0, 4],
                    [2, 3], [4, 5], [5, 6],
                    [5, 7]];
let N = edges.length;
for (let i = 0; i < N+1; i++)
    g.push([]);
 
for (let i = 0; i < N; i++)
    addEdge( edges[i][0], edges[i][1]);
 
 
document.write(maxEdgeRemovalToMakeForestEven( N));
 
// This code is contributed by rag2127
 
</script>

Producción: 

2

Complejidad de tiempo: O(n) donde n es el número de Nodes en el árbol.

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.