题目链接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;
}