Pat 1476 数叶子结点

题目

家庭关系可以用家谱树来表示，给定一个家谱树，你的任务是找出其中没有孩子的成员。

输入格式

第一行包含一个整数 N 表示树中结点总数以及一个整数 M 表示非叶子结点数。

接下来 M 行，每行的格式为：

ID K ID[1] ID[2] ... ID[K]

ID 是一个两位数字，表示一个非叶子结点编号，K 是一个整数，表示它的子结点数，接下来的 K 个 ID[i] 也是两位数字，表示一个子结点的编号。

为了简单起见，我们将根结点固定设为 01。

所有结点的编号即为 01, 02, 03, … ,31, 32, 33, …, N。

输出格式

输出从根结点开始，自上到下，树的每一层级分别包含多少个叶子节点。

输出占一行，整数之间用空格隔开。

数据范围

0 < N < 100

输入样例：

2 1
01 1 02

输出样例：

0 1

样例解释

该样例表示一棵只有 2 个结点的树，其中 01 结点是根，而 02 结点是其唯一的子节点。

因此，在根这一层级上，存在 0 个叶结点；在下一个级别上，有 1 个叶结点。

所以，我们应该在一行中输出0 1。

题解

1. 此题大概意思是给定一棵树(图)，求树的每一层的叶子结点数。

   

2. 根据输入数据构造出树 vector<int> node[N]

3. 用DFS求树的每层叶子结点数，从根结点01开始：

   1. 如果该结点是叶结点，该层叶子结点数+1，返回；
   2. 如果该结点不是叶结点，DFS遍历此结点的所有孩子结点。

    // 根据输入构造树
    vector<int> node[N];    // 采用临接表存储树
    while (m--) {
        int id, k, ch;
        cin >> id >> k;
        while (k--){
            cin >> ch;
            node[id].push_back(ch);
        }
    }
    // 深度优先搜索遍历树
    void dfs(int id, int depth)
    {
        if (node[id].size() == 0) {  // 递归出口
            leaveNum[depth]++;
            if (depth > maxDepth) {
                maxDepth = depth;
            }
            return;
        } else {
            for(auto n : node[id]) {  // 子问题调用
                bfs(n, depth + 1);
            }
        }
    }