PAT Advanced 1094 The Largest Generation (25) [BFS,DFS,树的遍历]
题目
A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.
Input Specification:
Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:
ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.
Sample Input:
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
Sample Output:
9 4
题目分析
已知每个节点的所有子节点,求节点最多的层数max_num_h及对应层结点数max_num
解题思路
思路 01(最优)
邻接表存储树,dfs深度优先遍历树(当前节点所在层级用函数参数记录),int cndn[n]记录每层节点数,并更新max_num和max_num_h
思路 02
邻接表存储树,bfs深度优先遍历树(当前节点所在层级用int h[n]记录),int cndn[n]记录每层节点数,并更新max_num和max_num_h
易错点
题目理解错误,求的是节点最多的层(而不是节点最多的分支),求的是节点最多的层(而不是叶结点最多的层)
Code
Code 01(dfs 最优)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn=110;
vector<int> nds[maxn];
int cnds[maxn];//cnds[i] 记录i层结点总数
int max_num,max_num_h;//max_num树的宽度;max_num_h 结点数最多的层数;
void dfs(int now, int h) {
cnds[h]++;
if(max_num<cnds[h]) { //更新最多结点的层数信息
max_num_h=h; //层最多结点数 (树的宽度)
max_num=cnds[h]; //最多结点数的层号
}
if(nds[now].size()==0)return;
for(int i=0; i<nds[now].size(); i++) { //遍历当前结点所有子结点,进行dfs遍历
dfs(nds[now][i],h+1); // 当前结点的子结点所在层数=当前结点层数+1
}
}
int main(int argc,char * argv[]) {
int n,m,id,k,cid;
scanf("%d %d",&n,&m); //n结点总数;m非叶子结点数
for(int i=0; i<m; i++) { //输入所有非叶子结点的所有子节点信息
scanf("%d %d",&id,&k); //id 父结点编号;k该父结点有多少个子结点
for(int j=0; j<k; j++) {
scanf("%d", &cid);
nds[id].push_back(cid); //保存每个孩子到其父结点的容器中
}
}
dfs(1,1);
printf("%d %d",max_num,max_num_h);
return 0;
}
Code 02(bfs)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn=110;
vector<int> nds[maxn];
int h[maxn];//h[i] 记录i结点所在层数
int cnds[maxn];//cnds[i] 记录i层结点总数
int max_num,max_num_h;//max_num树的宽度;max_num_h 结点数最多的层数;
void bfs() {
queue<int> q;//bfs需要借助队列实现
q.push(1); //根结点编号为1
while(!q.empty()) {
int now = q.front();
q.pop();
cnds[h[now]]++;
if(max_num<cnds[h[now]]) { //更新最多结点的层数信息
max_num_h=h[now]; //层最多结点数 (树的宽度)
max_num=cnds[h[now]]; //最多结点数的层号
}
for(int i=0; i<nds[now].size(); i++) { //遍历当前结点所有子结点,进行bfs遍历
h[nds[now][i]]=h[now]+1; // 当前结点的子结点所在层数=当前结点层数+1
q.push(nds[now][i]);
}
}
}
int main(int argc,char * argv[]) {
int n,m,id,k,cid;
scanf("%d %d",&n,&m); //n结点总数;m非叶子结点数
for(int i=0; i<m; i++) { //输入所有非叶子结点的所有子节点信息
scanf("%d %d",&id,&k); //id 父结点编号;k该父结点有多少个子结点
for(int j=0; j<k; j++) {
scanf("%d", &cid);
nds[id].push_back(cid); //保存每个孩子到其父结点的容器中
}
}
h[1]=1;
bfs();
printf("%d %d",max_num,max_num_h);
return 0;
}
最新文章
- UGUI&;&;Animator模块知识点随记
- React Native 重新建项目遇到的一些问题
- makefile中的自动化变量$@,$%,$
- 单点登陆CAS安装过程中可能遇到的问题
- 使用nodejs的http模块创建web服务器
- Android智能手机上的音频浅析
- Microsoft Dynamics CRM 2013/2015 选项集的多选
- Code Review Checklist
- windows环境jprofiler配置监控tomcat
- (转)Spring Boot 2 (二):Spring Boot 2 尝鲜-动态 Banner
- Hadoop格式化 From hu-hadoop1/192.168.11.11 to hu-hadoop2:8485 failed on connection exception: java.net.
- 7个华丽的基于Canvas的HTML5动画
- ELKStack生产案例
- 安装cartographer_ros
- Trace VM
- UVA-1149 Bin Packing (贪心)
- 北京Uber优步司机奖励政策(4月10日)
- python 有关引用的一些问题
- 北京Uber优步司机奖励政策(2月26日)
- caffe Python API 之Dropout
热门文章
- 10 MySQL索引选择与使用
- 关于cvPyrSegmentation(src, dst, storage, &;comp, level, threshold1, threshold2)函数报错的问题解答
- CSS隐藏商务通等内容
- 基础知识 SafeSEH DEP ASLR SEHOP
- LeetCode实战练习题目 - Array
- Rabbitmq之高级特性——实现消费端限流&;NACK重回队列
- 云时代架构阅读笔记二——Java性能优化(二)
- 075-PHP数组添加元素
- SQL分组后获取其中一个字段最大值的整条记录
- SpringMVC: Ajax技术