1094. The Largest Generation.md

【PAT A-1094】The Largest Generation

题意概述

找到树中结点最多的层。

输入输出格式

输入第一行先给出 3 个正整数 N、M，分别表示树中的结点数，树中非叶子结点数。接下来 M 行，每行先给出一个 ID，接着给出一个正整数 K，紧跟着给出 K 个正整数，这 K 个正整数均为结点 ID 的子结点。根结点的 ID 是 1。

输出结点最多的层的结点数和层号。根结点所在的层号为 1。

数据规模

$$0<M<N<100$$

算法设计

既然与层次有关，使用 BFS 是最好的。当然你也可以使用 DFS，但会比 BFS 稍微麻烦一些。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 105;
vector<vector<gg>> tree(MAX);
gg ni, mi, ki;
void bfs(gg root) {
    queue<gg> q;
    q.push(root);
    gg level = 0, ansLevel = 0, ansNum = 0;
    while (not q.empty()) {
        gg s = q.size();
        ++level;
        if (s > ansNum) {
            ansNum = s;
            ansLevel = level;
        }
        for (gg i = 0; i < s; ++i) {
            auto t = q.front();
            q.pop();
            for (auto i : tree[t]) {
                q.push(i);
            }
        }
    }
    cout << ansNum << " " << ansLevel;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> mi;
    for (gg i = 0; i < mi; ++i) {
        gg ti, ai;
        cin >> ti;
        cin >> ki;
        while (ki--) {
            cin >> ai;
            tree[ti].push_back(ai);
        }
    }
    bfs(1);
    return 0;
}