PAT_A1094#The Largest Generation
Source:
Description:
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 (<) 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 (<) 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
(>) is the number of his/her children, followed by a sequence of two-digitID
's of his/her children. For the sake of simplicity, let us fix the rootID
to be01
. 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
Keys:
Code:
/*
time: 2019-08-24 15:25:08
problem: PAT_A1094#The Largest Generation
AC: 18:52 题目大意:
求树中结点个数最多的层次及其结点个数 基本思路:
遍历并统计各层次人数即可
*/
#include<cstdio>
#include<vector>
using namespace std;
const int M=1e3;
vector<int> tree[M];
int scale[M]={},largest=,generation; void Travel(int root, int layer)
{
scale[layer]++;
if(scale[layer] > largest)
{
largest = scale[layer];
generation = layer;
}
for(int i=; i<tree[root].size(); i++)
Travel(tree[root][i],layer+);
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE int n,m,id,k,kid;
scanf("%d%d", &n,&m);
for(int i=; i<m; i++)
{
scanf("%d%d", &id,&k);
for(int j=; j<k; j++)
{
scanf("%d", &kid);
tree[id].push_back(kid);
}
}
Travel(,);
printf("%d %d", largest,generation); return ;
}
最新文章
- Pairing heap
- 【GoLang】golang中可以直接返回slice吗?YES
- linux中的基础正则表达式
- 【Unity3D基础】让物体动起来②--UGUI鼠标点击逐帧移动
- BaaS服务的定义、发展以及未来
- AjaxPro框架
- goldengate的HANDLECOLLISIONS参数
- (转)C#中的泛型
- 几种MEMS陀螺仪(gyroscope)的设计和性能比较
- 简单理清一下proto与prototype
- 闲聊select和input常用的小插件
- python入门 -- 环境搭建(windows)
- 使用IDEA2017在Windows下编程并测试Hadoop2.7+Spark2.2+Azkaban
- swoole之代码热更新实现 转自https://blog.csdn.net/nep_tune/article/details/81329918
- js实现上传图片回显功能
- .Net MVC Cache 缓存技术总结
- python自学第三天,列表
- Javascript class获取回调函数数据
- 解决kafka集群由于默认的__consumer_offsets这个topic的默认的副本数为1而存在的单点故障问题
- 蓝桥杯 - 数字排列(今有7对数字) - [两种不同的DFS思路]
热门文章
- 出现Warning: date(): It is not safe to rely on the system&#39;s timezone settings的解决办法
- 用 Windows Live Writer 和 SyntaxHighlighter 插件写高亮代码
- Hyperledger:名词解释
- 线性回归——Python代码实现
- Java中static关键字,this关键字
- 使用wireshark在windows平台下捕获HTTP协议数据包中的帐号密码信息
- sudo dpkg --configure -a无法解决的问题
- 随笔记录 yum -y clean all出错解决方案
- nodejs 模板引擎ejs的简单使用(2)
- Oracle使用——PLSQL的中文乱码显示全是问号--Oracle查询中文乱码