PAT 1004 Counting Leaves
程序员文章站
2022-06-11 15:10:39
...
题目描述
英文
中文大意
通过输入的树找出 每一层有多少个叶子节点
样例输出
思路分析
用 dfs 深度优先遍历, 大致思路是寻找叶子节点, 如果找到在 record[]
数组对应的深度depth
加一
理解一下各个输入
- N: 节点个数
- M: 非叶子节点个数
- ID: 非叶子节点标识
- K: 此节点的儿子节点数
- ID[i]: 此节点的儿子节点
首先接受 N、M, 叶子节点不用统计,所以根据M 获取节点
把每个节点的子节点都存入 vector[index]
通过判断vector[index].size() 是否为 0 来判断是否为叶子节点
由于我本人对于 vector 的使用不是很熟悉, 导致 这个
vector[]
的用法还是参考的别人代码
vector 不是一个动态数组吗?为什么可以通过 vector[index].size()
使用, 此用法有些类似 有序哈希表
code
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100];
int record[100];
// 深度优先遍历
void dfs(int index, int depth) {
// 遇到叶节点
if(v[index].size() == 0) {
record[depth]++;
return;
}
// 递归
for(int i = 0;i < v[index].size();i++) {
dfs(v[index].at(i), depth+1);
}
}
int main() {
int N, M, index, K, node, cnt = 0;
cin >> N >> M;
for(int i = 0;i < M;i++) {
cin >> index >> K;
for(int j = 0;j < K;j++) {
cin >> node;
v[index].push_back(node);
}
}
dfs(1, 1);
// cnt 用于记数 N -M 是叶子节点的总数
for(int i = 1;cnt != N-M;i++) {
if (i == 1) cout << record[i];
else cout << " " << record[i];
// cnt 记录
cnt += record[i];
}
return 0;
}
题目链接
参考文章
下一篇: 什么是ORM,以及在php上的使用?