PAT(Advanced)1094 The Largest Generation 先序遍历 C++实现
PAT(Advanced)甲级1094 The Largest Generation 先序遍历 C++实现
题目链接
1094 The Largest Generation
题目大意
给定家族树，求解人数最多的一代，输出最多人数和那一代的代数，保证答案唯一
算法思路
根据题目要求和树的先序遍历定义，遍历整棵树，对应的层数累加，最后遍历所有层的节点数得到最大值即可
void preOrderTraverse(int currentLevel, int order) {level[currentLevel]++;for (int i = 0; i < tree[order].size(); i++) {preOrderTraverse(currentLevel + 1, tree[order][i]);}
}
AC代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Sun Jun 28 11:35:09 2020
*/
#include <bits/stdc++.h>
using namespace std;vector<vector<int> > tree;
vector<int> level;void preOrderTraverse(int currentLevel, int order) {level[currentLevel]++;for (int i = 0; i < tree[order].size(); i++) {preOrderTraverse(currentLevel + 1, tree[order][i]);}
}void print() {int levelOrder = 0;for (int i = 1; i < level.size(); i++) {if (level[levelOrder] < level[i]) {levelOrder = i;}}printf("%d %d", level[levelOrder], levelOrder);
}int main(int argc, char const *argv[]) {int N, M;scanf("%d%d", &N, &M);tree.resize(N + 1);for (int i = 0; i < M; i++) {int ID, K;scanf("%d%d", &ID, &K);for (int j = 0; j < K; j++) {int child;scanf("%d", &child);tree[ID].push_back(child);}}level.resize(N + 1);preOrderTraverse(1, 1);print();return 0;
}样例输入
23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18
样例输出
9 4
鸣谢
PAT
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
PAT(Advanced)1094 The Largest Generation 先序遍历 C++实现
PAT(Advanced)甲级1094 The Largest Generation 先序遍历 C++实现
题目链接
1094 The Largest Generation
题目大意
给定家族树，求解人数最多的一代，输出最多人数和那一代的代数，保证答案唯一
算法思路
根据题目要求和树的先序遍历定义，遍历整棵树，对应的层数累加，最后遍历所有层的节点数得到最大值即可
void preOrderTraverse(int currentLevel, int order) {level[currentLevel]++;for (int i = 0; i < tree[order].size(); i++) {preOrderTraverse(currentLevel + 1, tree[order][i]);}
}
AC代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Sun Jun 28 11:35:09 2020
*/
#include <bits/stdc++.h>
using namespace std;vector<vector<int> > tree;
vector<int> level;void preOrderTraverse(int currentLevel, int order) {level[currentLevel]++;for (int i = 0; i < tree[order].size(); i++) {preOrderTraverse(currentLevel + 1, tree[order][i]);}
}void print() {int levelOrder = 0;for (int i = 1; i < level.size(); i++) {if (level[levelOrder] < level[i]) {levelOrder = i;}}printf("%d %d", level[levelOrder], levelOrder);
}int main(int argc, char const *argv[]) {int N, M;scanf("%d%d", &N, &M);tree.resize(N + 1);for (int i = 0; i < M; i++) {int ID, K;scanf("%d%d", &ID, &K);for (int j = 0; j < K; j++) {int child;scanf("%d", &child);tree[ID].push_back(child);}}level.resize(N + 1);preOrderTraverse(1, 1);print();return 0;
}样例输入
23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18
样例输出
9 4
鸣谢
PAT
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
发布评论