【PAT-Advanced】1004 Counting Leaves

发表于 | 分类于 ， | | 阅读次数:

Problem

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 0<$N$<100, the number of nodes in a tree, and $M (<N)$, the number of non-leaf nodes. Then $M$ lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID‘s of its children. For the sake of simplicity, let us fix the root ID to be 01.

The input ends with $N$ being 0. That case must NOT be processed.

Output Specification:

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.

Sample Input:

2 1
01 1 02

Sample Output:

0 1


Solution

这题只要根据输入构建一颗树，记录每个节点的child, parent以及level，然后做一个层序遍历，输出每一层没有子节点的节点数即可。

这里有一个trick，关于level值的更新。发现测试点中大概ID从顶层往下依次增加，并且录入的顺序从小到大，这使得树的构建减少了根据新的父子关系更新整棵子树level值的情况。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

#define MAXN 105

using namespace std;

int M = 0; //number of non-leaf nodes
int N = 0; //number of nodes
int leafNum[MAXN];

struct node {
    int child_num;
    int level;
    int parent_id;
}Node[MAXN];

void init(){
    for(int i=0; i<MAXN; i++){
        Node[i].child_num = 0;
        Node[i].level = 0;
        Node[i].parent_id = 0;
        leafNum[i] = 0;
    }
}

int main(int argc, const char * argv[]) {
    init();
    cin >> N >> M;
    if(N == 0 || M > N){
        return 0;
    }
    int id, child_id;
    for(int i=0; i<M; i++){
        cin >> id;
        cin >> Node[id].child_num;
        for(int j=0; j<Node[id].child_num; j++){
            cin >> child_id;
            Node[child_id].parent_id = id;
            //如果会出现乱序情况，大概要在这里加更新level值，
            //并且要加判断，如果child有子节点，则在更新了level之后也要顺便更新子树所有节点的level
        }
    }
    Node[1].level = 0;
    for(int i=2; i<=N; i++){
        Node[i].level = Node[Node[i].parent_id].level + 1;
    }
    int maxlevel = 0;
    for(int i=1; i<=N; i++){
        if(Node[i].level > maxlevel){
            maxlevel = Node[i].level;
        }
        if(Node[i].child_num == 0){
            leafNum[Node[i].level]++;
        }
    }
    for(int i=0; i<maxlevel; i++){
        cout << leafNum[i] << " ";
    }
    cout << leafNum[maxlevel] << endl;
    return 0;
}

后来在网上发现另外一个做法，用的dfs，还挺妙，代码贴在下面，也可以看原博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>tree(100);//下标存储结点编号，元素内容存储儿子结点编号
int leaveNumOfLevel[100],maxLevel=-1;//每层叶子节点数、最大层数
int N,M;
void DFS(int v,int level){//深度优先遍历
    maxLevel=max(level,maxLevel);//更新最大层数
    if(tree[v].empty())//如果没有儿子结点，则为叶节点
        ++leaveNumOfLevel[level];//递增该节点所处层数下的叶节点数目
    for(int i:tree[v])//不是叶节点
        DFS(i,level+1);//递归遍历儿子结点
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int id,k;
        scanf("%d%d",&id,&k);
        while(k--){
            int iid;
            scanf("%d",&iid);
            tree[id].push_back(iid);
        }
    }
    DFS(1,0);
    for(int i=0;i<=maxLevel;++i)//输出每层叶子节点数
        printf("%s%d",i==0?"":" ",leaveNumOfLevel[i]);
    return 0;
}