PAT甲级Counting leaves

PAT甲级Counting leaves题解

原题

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
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.
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.

翻译

一个家族通常用一棵家族树表示，你的个工作是数出没有孩子的家庭成员. 每一个输入文件包含一个测试点，每个测试点包含一个` N 0< N < 100` 表示树中的节点数，以及M表示飞叶节点的个数，接啥来的M行每行的格式为：`ID K ID[1] ID[2] ... ID[K]` 其中ID是一个两位数表示非叶节点，K是它孩子的个数，然后依次是他的孩子节点的ID，为了简单起见，我们假设根节点为01。 对于每一个测试点，你应该数出每一层叶节点的个数。中间用空格分隔，末尾没有多语空格。

思路

广度优先搜索,记录每一层叶节点个数

程序

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int id;
    vector<int> child;
};
int main()
{
    int n, m;
    cin >> n >> m;
    node f[n + 1];
    int id, num, c;
    for (int i = 0; i < m; i++)
    {
        cin >> id >> num;
        for (int j = 0; j < num; j++)
        {
            cin >> c;
            f[id].child.push_back(c);
        }
    }
    //队列
    queue<int> q;
    q.push(1);
    int flag = 1;
    //广度优先
    while (!q.empty())
    {
      //计数（此层叶节点）
        int count = 0;
        //提前记录当前队列中的元素个数（此层的节点数，防止循环内部push导致无法分层）
        int l = q.size();
        //遍历此层每个节点
        for (int j = 0; j < l; j++)
        {
          //叶节点
            if (f[q.front()].child.size() == 0)
            {
                count++;
            }
            //将每个节点的孩子入队
            for (int i = 0; i < f[q.front()].child.size(); i++)
            {
                q.push(f[q.front()].child[i]);
            }
            //出队头结点
            q.pop();
        }
        //输出
        if (flag)
        {
            cout << count;
            flag = 0;
        }
        else
        {
            cout << ' ' << count;
        }
    }
}