202504252100 1004 Counting Leaves

家族树叶子节点统计

家族层次结构通常由谱系树表示。您的任务是统计每个辈分层级中没有孩子的家庭成员数量。

输入规范：

每个输入文件包含一个测试用例。每个用例以一行开始，包含 $0<N<100$（树中的节点数）和 $M<N$（非叶子节点的数量）。然后是 $M$ 行，每行格式如下：

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

其中 ID 是表示给定非叶子节点的两位数字，K 是其子节点的数量，后面是一个两位数字 ID 序列，表示其子节点。为简单起见，我们将根节点 ID 固定为 01。

输入以 N 为 0 结束。该情况不需要处理。

输出规范：

对于每个测试用例，您需要从根节点开始，统计每个辈分层级中没有孩子的家庭成员数量。这些数字必须在一行中打印，用空格分隔，行末不能有多余的空格。

样例表示一棵只有 2 个节点的树，其中 01 是根节点，02 是它唯一的子节点。因此，在根节点 01 层级上，有 0 个叶子节点；在下一层级，有 1 个叶子节点。所以我们应该输出 0 1。

样例输入：

2 1
01 1 02

样例输出：

0 1

Solve

节点ID有两位数组成，可知节点数为 $1-99$ ，让我们输出每一行中的叶子节点个数。

故先存入图，由于存入时为先知道一个节点然后存其子节点，则可以在存入时使用 hasChild 来标记当前节点为有孩子，这样存完图后没有标记的就是有子节点的节点。

而之后使用 bfs 来进行层序遍历，核心思想为每轮遍历是当前层级的所有节点，同时为保证每个节点只访问一次，需要在加入队列时进行标记 visited。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int main() {
 
    int n, m;
    while(cin >> n && n != 0) {
        cin >> m;
 
        vector<vector<int>> family(100);
        vector<bool> hasChild(100, false);
 
        while(m--) {
            int parent, k;
            cin >> parent >> k;
 
            hasChild[parent] = true;
 
 
            for(int i = 0; i < k; i++) {
                int child;
                cin >> child;
                family[parent].push_back(child);
            }
        }
 
        queue<int> q;
        vector<bool> visited(100, false);
        q.push(1);
        visited[1] = true;
 
        vector<int> res;
        
        while(q.size()) {
            int levelSize = q.size();
            int levelLeaf = 0;
 
            for(int i = 0; i < levelSize; i++) {
                int current = q.front();
                q.pop();
 
                if(!hasChild[current])
                    levelLeaf++;
 
                for(int children : family[current]) {
                    if(!visited[children]) {
                        visited[children] = true;
                        q.push(children);
                    }
                }
            }
 
            res.push_back(levelLeaf);
        }
 
        for(int i = 0; i < res.size();i ++)
            cout << res[i] << " \n"[i==res.size()-1];
        
    }
    return 0;
}