个人练习- PAT甲级-1094 The Largest Generation

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805372601090048

题号居然又改回去了，真是神奇。。。

题目大意是：给定一个家族人数和有孩子的人数，并给出父亲和孩子的编号。固定01号为根结点。求人数最多的层数及该层人数。

开始时不太想建树，想了半天不用建树的方法。但因为在输入中，01及其孩子的出现的顺序并不是固定的，想要在第一遍扫描时就确定层数比较困难，回溯算层数也一样要把数据先存一遍，于是放弃了。

方法还是建树，用DFS。每一个节点都遍历到一遍，lv2num输入层数，得到该层人数。

void DFS(int id, int lv) {
    lv2num[lv]++;for (int i = 0; i < mat[id].size(); i++) {
    DFS(mat[id][i], lv+1);}
}

另外注意下总人数为0的情况就好。

完整代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>using namespace std;
const int MAXN = 101;
vector<int> mat[MAXN];
int lv2num[MAXN];void DFS(int id, int lv) {
    lv2num[lv]++;for (int i = 0; i < mat[id].size(); i++) {
    DFS(mat[id][i], lv+1);}
}int main() {
    int N, M;scanf("%d %d", &N, &M);for (int i = 0; i < M; i++) {
    int tmp_id, K;scanf("%d %d", &tmp_id, &K);for (int j = 0; j < K; j++) {
    int child;scanf("%d", &child);mat[tmp_id].push_back(child);}}DFS(1, 1);int ret_lv = 0, ret_num = 0;for (int i = 1; i <= N; i++) {
    if (lv2num[i] == 0)break;if (lv2num[i] > ret_num) {
    ret_lv = i;ret_num = lv2num[i];}}printf("%d %d", ret_num, ret_lv);return 0;
}