从具有偶数个节点的树中获取森林 [英] Obtain forest out of tree with even number of nodes
问题描述
我遇到了代码挑战，我想要一个提示。
I'm stuck on a code challenge, and I want a hint.
问题：您被赋予树数据结构（无循环），并被要求删除尽可能多的边缘（连接），从而创建具有偶数节点的较小树。这个问题总是可以解决的，因为节点和连接的数量是偶数。
PROBLEM: You are given a tree data structure (without cycles) and are asked to remove as many "edges" (connections) as possible, creating smaller trees with even numbers of nodes. This problem is always solvable as there are an even number of nodes and connections.
您的任务是计算已删除的边。
Your task is to count the removed edges.
输入：
输入的第一行包含两个整数N和M。N是顶点数，M是边数。 2< = N< =100。
接下来的M行包含两个整数ui和vi，它们指定树的边缘。 （从1开始的索引）
Input: The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100. Next M lines contains two integers ui and vi which specifies an edge of the tree. (1-based index)
输出：
打印已删除的边数。
Output: Print the number of edges removed.
样本输入
10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8 < br>
10 9
2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8
样本输出：
2
Sample Output : 2
说明：去除边缘（1、3 ）和（1，6），我们可以获得预期的结果。
Explanation : On removing the edges (1, 3) and (1, 6), we can get the desired result.
推荐答案
我使用BFS在节点之间移动。
首先，单独维护一个数组以存储子节点的总数+1。
因此，您可以首先在此数组中分配所有值为1的叶子节点。
现在从最后一个节点开始，并计算每个节点的子代数。这将以自下而上的方式工作，并且存储子节点数的数组将在运行时帮助优化代码。
I used BFS to travel through the nodes. First, maintain an array separately to store the total number of child nodes + 1. So, you can initially assign all the leaf nodes with value 1 in this array. Now start from the last node and count the number of children for each node. This will work in bottom to top manner and the array that stores the number of child nodes will help in runtime to optimize the code.
所有节点的子节点数，仅计算节点数为偶数的节点即可得出答案。注意：在最后一步中，我没有包括根节点。
Once you get the array after getting the number of children nodes for all the nodes, just counting the nodes with even number of nodes gives the answer. Note: I did not include root node in counting in final step.
这篇关于从具有偶数个节点的树中获取森林的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
