algorithm - tipos - metodo chaid de arboles de decision

Obtener bosque fuera de árbol con un número par de nodos

Question

Estoy atrapado en un desafío de código, y quiero una pista .

PROBLEMA : Se le proporciona una estructura de datos de árbol (sin ciclos) y se le pide que elimine tantos "bordes" (conexiones) como sea posible, creando árboles más pequeños con números pares de nodos. Este problema siempre se puede resolver ya que hay un número par de nodos y conexiones.

Tu tarea es contar los bordes eliminados.

Entrada: la primera línea de entrada contiene dos enteros N y M. N es el número de vértices y M es el número de aristas. 2 <= N <= 100. Las siguientes líneas M contienen dos enteros ui y vi que especifican un borde del árbol. (Índice basado en 1)

Salida: Imprime el número de bordes eliminados.

Entrada de muestra

10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

Salida de muestra: 2

Explicación: Al quitar los bordes (1, 3) y (1, 6), podemos obtener el resultado deseado.

Answer 1

Aquí está el esquema general de un enfoque alternativo:

1. Encuentra todos los puntos de articulación en el gráfico.
2. Compruebe cada punto de articulación para ver si se pueden eliminar los bordes allí.
3. Elimine los bordes legales y busque más puntos de articulación.

Answer 2

Esta es mi solución. No usé el árbol bfs, solo asigné otro arreglo para mantener el número total de nodos de cada nodo y sus hijos.

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
        public static void main(String[] args) {
                int tree[];
                int count[];

                Scanner scan = new Scanner(System.in);

                int N = scan.nextInt(); //points
                int M = scan.nextInt();

                tree = new int[N];
                count = new int[N];
                Arrays.fill(count, 1);

                for(int i=0;i<M;i++)
                {
                        int u1 = scan.nextInt();
                    int v1 = scan.nextInt();

                    tree[u1-1] = v1;

                    count[v1-1] += count[u1-1];

                    int root = tree[v1-1];

                    while(root!=0)
                    {
                        count[root-1] += count[u1-1];
                        root = tree[root-1];
                    }
                }

                System.out.println("");

                int counter = -1;
                for(int i=0;i<count.length;i++)
                {
                        if(count[i]%2==0)
                        {
                                counter++;
                        }

                }
                System.out.println(counter);

        }

}

Answer 3

Este es el enfoque que utilicé para pasar con éxito todos los casos de prueba.

1. Marque el vértice 1 como la raíz
2. Comenzando en el vértice raíz actual, considere cada niño. Si la suma total del niño y todos sus hijos es pareja, entonces puede cortar esa ventaja
3. Descienda al siguiente vértice (hijo del vértice raíz) y deje que sea el nuevo vértice raíz. Repita el paso 2 hasta que haya atravesado todos los nodos (búsqueda de profundidad en la primera búsqueda).

Answer 4

Mi primera inclinación es trabajar desde los nodos de las hojas porque no puedes cortar sus bordes ya que eso dejaría subárboles de un solo vértice.

Answer 5

Sé que esto ya ha sido respondido aquí muchísimo tiempo. Todavía quiero saber las opiniones sobre mi solución aquí. Intenté construir el recuento de niños a medida que los bordes pasaban por la entrada y pasó todos los casos de prueba.

namespace Hackerrank
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    class Program
    {
        static void Main(string[] args)
        {
            var tempArray = Console.ReadLine().Split('' '').Select(x => Convert.ToInt32(x)).ToList();
            int verticeNumber = tempArray[0];
            int edgeNumber = tempArray[1];

            Dictionary<int, int> childCount = new Dictionary<int, int>();

            Dictionary<int, int> parentDict = new Dictionary<int, int>();

            for (int count = 0; count < edgeNumber; count++)
            {
                var nodes = Console.ReadLine().Split('' '').Select(x => Convert.ToInt32(x)).ToList();
                var node1 = nodes[0];
                var node2 = nodes[1];

                if (childCount.ContainsKey(node2))
                    childCount[node2]++;
                else childCount.Add(node2, 1);

                var parent = node2;
                while (parentDict.ContainsKey(parent))
                {
                    var par = parentDict[parent];
                    childCount[par]++;
                    parent = par;
                }

                parentDict[node1] = node2;
            }

            Console.WriteLine(childCount.Count(x => x.Value % 2 == 1) - 1);
        }
    }
}

Answer 6

Si observa la entrada, puede ver que es bastante fácil contar la cantidad de nodos debajo de cada nodo. Considere (ab) como la entrada de borde, en cada caso, a es el niño yb es el padre inmediato. La entrada siempre tiene bordes representados de abajo hacia arriba.

Por lo tanto, es esencialmente el número de nodos que tienen un conteo par (excluyendo el nodo raíz). Envié el código siguiente en Hackerrank y todas las pruebas pasaron. Supongo que todos los casos en la entrada satisfacen la regla.

def find_edges(count):
    root = max(count)

    count_even = 0

    for cnt in count:
        if cnt % 2 == 0:
            count_even += 1

    if root % 2 == 0:
        count_even -= 1

    return count_even

def count_nodes(edge_list, n, m):
    count = [1 for i in range(0, n)]

    for i in range(m-1,-1,-1):
        count[edge_list[i][1]-1] += count[edge_list[i][0]-1]

return find_edges(count)

Answer 7

Solución: recorra todos los bordes y cuente el número de bordes pares

Si eliminamos un borde del árbol y resulta en dos árboles con un número par de vértices, llamemos ese borde, incluso el borde

Si eliminamos un borde del árbol y resulta en dos árboles con un número impar de vértices, vamos a llamar a ese borde - borde impar

Aquí está mi solución en Ruby

num_vertices, num_edges = gets.chomp.split('' '').map { |e| e.to_i }
graph = Graph.new
(1..num_vertices).to_a.each do |vertex|
  graph.add_node_by_val(vertex)
end

num_edges.times do |edge|
  first, second = gets.chomp.split('' '').map { |e| e.to_i }
  graph.add_edge_by_val(first, second, 0, false)
end

even_edges = 0
graph.edges.each do |edge|
  dup = graph.deep_dup
  first_tree = nil
  second_tree = nil
  subject_edge = nil
  dup.edges.each do |e|
    if e.first.value == edge.first.value && e.second.value == edge.second.value
      subject_edge = e
      first_tree = e.first
      second_tree = e.second
    end
  end
  dup.remove_edge(subject_edge)
  if first_tree.size.even? && second_tree.size.even?
    even_edges += 1
  end
end
puts even_edges

Nota: haga clic aquí para ver el código de las clases Graph, Node y Edge

Answer 8

Usé BFS para viajar a través de los nodos. Primero, mantenga una matriz por separado para almacenar la cantidad total de nodos secundarios + 1. Por lo tanto, puede asignar inicialmente todos los nodos hoja con el valor 1 en esta matriz. Ahora comience desde el último nodo y cuente la cantidad de hijos para cada nodo. Esto funcionará de abajo hacia arriba y la matriz que almacena la cantidad de nodos secundarios ayudará en el tiempo de ejecución a optimizar el código.

Una vez que obtiene la matriz después de obtener la cantidad de nodos secundarios para todos los nodos, solo contar los nodos con un número par de nodos da la respuesta. Nota: No incluí el nodo raíz en el conteo en el paso final.