32

我被困在一个代码挑战中，我想要一个提示。

问题：给你一个树数据结构（没有循环），并被要求删除尽可能多的“边”（连接），创建具有偶数个节点的更小的树。这个问题总是可以解决的，因为有偶数个节点和连接。

你的任务是计算删除的边缘。

输入：输入的第一行包含两个整数 N 和 M。N 是顶点数，M 是边数。2 <= N <= 100。接下来的 M 行包含两个整数 ui 和 vi，它们指定了树的边缘。（基于 1 的索引）

输出：打印移除的边数。

样本输入

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

样本输出：2

解释 : 移除边 (1, 3) 和 (1, 6)，我们可以得到想要的结果。

4

8 回答 8

23

我使用 BFS 遍历节点。首先，单独维护一个数组来存储子节点的总数+1。因此，您可以在此数组中初始分配值为1的所有叶节点。现在从最后一个节点开始计算每个节点的子节点数。这将以自下而上的方式工作，存储子节点数量的数组将有助于在运行时优化代码。

在获得所有节点的子节点数后获得数组后，只需计算节点数为偶数的节点即可得到答案。注意：我没有在最后一步计算根节点。

于 2012-08-31T16:49:38.523 回答
6

这是我的解决方案。我没有使用 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);

        }

}
于 2012-10-26T00:50:50.317 回答
2

如果你观察输入，你会发现计算每个节点下的节点数是很容易的。将 (ab) 视为边缘输入，在每种情况下，a 都是孩子，b 是直接父母。输入始终具有自下而上表示的边缘。

所以它本质上是具有偶数计数的节点数（不包括根节点）。我在 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)
于 2013-08-06T21:40:21.827 回答
2

我知道这已经在这里得到了很多很多时间的回答。我仍然想在这里了解我的解决方案的评论。我试图构建子计数，因为边缘通过输入并且它通过了所有测试用例。

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);
        }
    }
}
于 2016-08-28T04:05:44.113 回答
1

我的第一个倾向是从叶节点开始工作，因为你不能切割它们的边缘，因为这会留下单顶点子树。

于 2012-08-20T18:53:29.047 回答
1

这是我用来成功通过所有测试用例的方法。

  1. 将顶点 1 标记为根
  2. 从当前根顶点开始，考虑每个孩子。如果孩子及其所有孩子的总和是偶数，那么你可以削减那条边
  3. 下降到下一个顶点（根顶点的子节点）并让它成为新的根顶点。重复步骤 2，直到遍历所有节点（深度优先搜索）。
于 2015-11-22T04:32:28.190 回答
0

以下是另一种方法的概要：

  1. 找出图中的所有关节点。
  2. 检查每个关节点，看看是否可以去除那里的边缘。
  3. 去除合法边缘并寻找更多的关节点。
于 2015-03-24T07:49:20.683 回答
0

解决方案 - 遍历所有边，并计算偶数边的数量

如果我们从树中删除一条边，它会导致两棵树的顶点数为偶数，我们称该边为偶数边

如果我们从树中删除一条边并导致两棵树的顶点数为奇数，我们称该边为奇数边

这是我在 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 类的代码

于 2015-10-19T03:13:01.573 回答