Получить лес из дерева с четным числом узлов

Ответ 1

Я использовал BFS для перемещения по узлам. Сначала сохраните массив отдельно, чтобы сохранить общее количество дочерних узлов + 1. Таким образом, вы можете сначала назначить все листовые узлы со значением 1 в этом массиве. Теперь начните с последнего node и подсчитайте количество детей для каждого node. Это будет работать сверху до конца, и массив, который хранит количество дочерних узлов, поможет во время выполнения оптимизировать код.

Как только вы получите массив после получения количества дочерних узлов для всех узлов, просто подсчет узлов с четным числом узлов даст ответ. Примечание. Я не включил root node в подсчет на последнем шаге.

Ответ 2

Это мое решение. Я не использовал дерево bfs, просто выделил другой массив для хранения общего числа узлов и их дочерних узлов.

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);

        }

}

Ответ 3

Если вы наблюдаете ввод, вы можете видеть, что подсчет количества узлов под каждым node довольно просто. Рассмотрим (a b) в качестве входного ребра, в каждом случае a является дочерним, а b - непосредственным родителем. Вход всегда имеет ребра, представленные снизу вверх.

Итак, по сути это число узлов, которые имеют четное число (исключая корень node). Я подал ниже код на Hackerrank и все тесты прошли. Я предполагаю, что все случаи ввода удовлетворяют правилу.

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)

Ответ 4

Я знаю, что на это уже были ответы много и много времени. Я все еще хочу узнать отзывы о своем решении здесь. Я попытался построить дочерний счет, когда края проходили через вход, и он прошел все тестовые примеры.

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);
        }
    }
}

Ответ 5

Мое первое наклонение состоит в том, чтобы работать с листовыми узлами, потому что вы не можете вырезать их края, поскольку они оставят одно вершинные поддеревья.

Ответ 6

Здесь подход, который я использовал для успешного прохождения всех тестовых случаев.

• Отметьте вершину 1 как корень
• Начиная с текущей корневой вершины, рассмотрим каждый ребенок. Если общая сумма ребенка и всех его детей ровная, вы можете сократить этот край.
• Спуститесь к следующей вершине (дочерняя вершина корневой вершины) и пусть это будет новая корневая вершина. Повторите шаг 2, пока не пройдете все узлы (сначала поиск по глубине).

Ответ 7

Здесь общий план альтернативного подхода:

• Найти все точки сочленения на графике.
• Проверьте каждую точку сочленения, чтобы увидеть, могут ли быть удалены края.
• Удалите левые края и найдите дополнительные точки сочленения.

Ответ 8

Решение. Переместите все ребра и подсчитайте количество четных ребер

Если мы удалим ребро из дерева и получим два дерева с четным числом вершин, позвольте называть это ребро четное ребро

Если мы удалим ребро из дерева и получим два дерева с нечетным количество вершин, пусть назовем ребро - нечетное ребро

Вот мое решение в 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

Примечание. Щелкните здесь, чтобы проверить код для Graph, Node и Edge classes