1004 Counting Leaves

注意点

1. n可能会是0(测试集好像没有出现这个情况)
2. n=1 m=0 应该输出1
3. 节点输入不一定按照顺序来，有可能是打乱的

如果先按照输入构造树的话可能会没有上面的注意点，可能我的想法比较奇怪

我之前写的python代码，然后第5个(编号是4)测试点过不去，报错非零返回，然后我用java重新翻译了一遍代码，就可以了，玄学

java代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main implements Comparable<Main>{
    
    int id;
    HashSet<Integer> set = new HashSet<Integer>();
    
    @Override
    public int compareTo(Main o) {
        return this.id-o.id;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int nodeNum = in.nextInt();
        int nodeNonleafNum = in.nextInt();
        Main[] mains = new Main[nodeNonleafNum];
        for(int i=0;i<nodeNonleafNum;i++) {
            Main main = new Main();
            main.id = in.nextInt();
            int n = in.nextInt();
            for(int j=0;j<n;j++) {
                main.set.add(in.nextInt());
            }
            mains[i] = main;
        }
        Arrays.sort(mains);
        ArrayList<HashSet> dataList = new ArrayList<HashSet>();
        if(nodeNum == 1) {
            System.out.println(1);
        }else if(nodeNum > 1) {
            HashSet<Integer> set1 = new HashSet<Integer>();
            set1.add(mains[0].id);
            dataList.add(set1);
            dataList.add(mains[0].set);
            int father = 0;
            int son = 1;
            for(int i=1;i<nodeNonleafNum;i++) {
                if(dataList.get(father).contains(mains[i].id)) {
                    dataList.get(father).remove(mains[i].id);
                    dataList.get(son).addAll(mains[i].set);
                }else if(dataList.get(son).contains(mains[i].id)) {
                    dataList.get(son).remove(mains[i].id);
                    dataList.add(mains[i].set);
                    father = son;
                    son++;
                }
            }
            System.out.print(0);
            for(int i=1;i<dataList.size();i++) {
                System.out.print(" " + dataList.get(i).size());
            }
        }
        in.close();
    }
}

python代码

node_num, node_nonleaf_num = map(int, input().split(' '))

data_list = []
for _ in range(node_nonleaf_num):
    data_list.append(input())

if node_num == 0:
    exit()

if node_nonleaf_num == 0:
    print(node_num)
    exit()

data_list.sort()

tree_list = []
father = 0
son = 1

line_list = list(map(int, data_list[0].split(" ")))
tree_list.append([])
tree_list.append(line_list[2:])

for line in data_list[1:]:
    line_list = list(map(int, line.split(" ")))  

    if line_list[0] in tree_list[father]:
        tree_list[father].remove(line_list[0])
        tree_list[son].extend(line_list[2:])

    elif line_list[0] in tree_list[son]:
        tree_list[son].remove(line_list[0])
        if len(tree_list) == son+1:
            tree_list.append(line_list[2:])
        else:
            tree_list[son+1].extend(line_list[2:])
        
        father = son
        son += 1

print(0, end="")
for item in tree_list[1:]:
    print(" " + str(len(item)), end="")

1004 Counting Leaves

原文：https://www.cnblogs.com/d-i-p/p/10644871.html