用偶数个节点从树中获取森林
我被卡在代码挑战，我想要一个提示 。
问题 ：给你一个树数据结构（没有周期），并被要求去除尽可能多的“边”（连接），创建更小的树，偶数个节点。 这个问题总是可以解决的，因为有偶数个节点和连接。
你的任务是计算删除的边缘。
输入：输入的第一行包含两个整数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）时，我们可以得到想要的结果。
我用BFS穿过节点。 首先，分别维护一个数组以存储子节点的总数+1。因此，您可以在此数组中初始分配值为1的所有叶节点。 现在从最后一个节点开始，并计算每个节点的子节点数量。 这将以自下而上的方式工作，存储子节点数量的数组将有助于运行时优化代码。
一旦获得所有节点的子节点数后得到数组，只需计算节点数为偶数的节点即可得出答案。 注意：在最后一步中，我没有包含根节点。
这是我的解决方案。 我没有使用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);
}
}
如果你观察输入，你可以看到很容易计算每个节点下的节点数量。 考虑（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)
上一篇: Obtain forest out of tree with even number of nodes
下一篇: What's the difference between the data structure Tree and Graph?