Bekommen Sie den Wald aus dem Baum mit einer geraden Anzahl von Knoten

Dies ist meine Lösung. Ich habe nicht verwenden bfs-Baum, nur reserviert ein array für die Abhaltung eachnode und deren Kinder-Knoten Gesamtzahl.

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

        }

}

InformationsquelleAutor der Antwort Eren Yagdiran

Ich weiß, dass dies schon beantwortet wurde hier viel, viel Zeit. Ich will immer noch wissen, Bewertungen auf meine Lösung hier. Ich habe versucht zu konstruieren das Kind zählen, da waren die Ränder kommen durch den Eingang und es bestanden alle den test Fällen.

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

InformationsquelleAutor der Antwort Swagata Prateek

Hier ist der Ansatz, den ich verwendet, um erfolgreich bestanden alle die Prüfung Fällen.

1. Mark vertex 1 als root
2. Beginnend mit der aktuellen root-vertex, betrachten Sie jedes Kind. Wenn die Gesamtsumme des Kindes und alle seine Kinder eben sind, dann können Sie schneiden, die Kante
3. Hinab auf den nächsten Eckpunkt (Kind des root-vertex) und lassen Sie, dass die neue root-vertex. Wiederholen Sie Schritt 2, bis Sie haben, Durchlaufen aller Knoten (depth first search).

InformationsquelleAutor der Antwort kldavis4

Lösung - Durchlaufen aller Kanten, und die Anzahl der noch Kanten

Wenn wir entfernen eine Kante aus dem Baum, und es ergibt sich in beiden Baum mit einer geraden Anzahl von Ecken, nennen wir ' s edge - auch edge

Wenn wir entfernen eine Kante aus dem Baum, und es ergibt sich in beiden Bäumen mit merkwürdig
Anzahl der Scheitelpunkte, sagen wir mal, dass edge - ungerade Kante

Hier ist meine Lösung in 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

Hinweis - Klicken Sie Hier zu überprüfen, die code für Graph, Node und Edge-Klassen

InformationsquelleAutor der Antwort satnam