使用偶数节点从树中获取森林

Question

我陷入了代码挑战,我想要一个提示.

问题:给你一个树数据结构(无环),并要求删除尽可能多的"边缘"(连接)成为可能,创造与节点的偶数小树林.由于存在偶数个节点和连接,因此始终可以解决此问题.

您的任务是计算删除的边缘.

输入:第一行输入包含两个整数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)时,我们可以得到所需的结果.

Answer 1

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

在获得所有节点的子节点数之后获得数组后,只计算具有偶数节点数的节点就可以得到答案.注意:我在最后一步计数中没有包含根节点.

Answer 2

这是我的解决方案.我没有使用bfs树,只是分配了另一个数组来保存eachnode和他们的子节点总数.

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

        }

}