AcWing 1584. 最大的一代
原题链接
简单
作者:
eveer
,
2021-09-03 19:28:51
,
所有人可见
,
阅读 446
#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>child[N];//储存孩子
int level[N];//层序存入
int nlevel[N];//记录每一个节点的层次
int l_cnt[N];//记录每一层的节点数量
void bfs(int root)
{
int tt=0,hh=0;
level[++tt]=root;
nlevel[tt]=1;//根节点的层次为1
while(tt>hh)
{
int para=level[++hh];//记录当前的父亲节点
if(child[para].size()!=0)//如果这个父亲有孩子,我们才往下继续摸索
{
for(int i=0;i<child[para].size();i++)
{
level[++tt]=child[para][i];//保存孩子
nlevel[tt]=nlevel[hh]+1;//在上一层的层次的基础上+1
}
}
}
}
int main()
{
int n,m;//n表示家庭成员的数量,m表示有孩子的节点数量
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)//遍历出所有孩子
{
int id,num;//id标记父亲,num表示这个父亲的孩子数量
scanf("%d%d",&id,&num);
for(int j=0;j<num;j++)
{
int x;//记录孩子
scanf("%d",&x);
child[id].push_back(x);
}
}
bfs(1);
int max_l=0;//记录当前最大层次
int max_n=0;//记录当前最大层次的节点数量
for(int i=1;i<=n;i++)//遍历每一个节点
l_cnt[nlevel[i]]++;//将这一层的节点数量+1
for(int i=1;i<=n;i++)
{
if(l_cnt[i]>max_n)
{
max_l=i;//表示最大数量为第i层
max_n=l_cnt[i];//表示该层的数量
}
}
printf("%d %d",max_n,max_l);
return 0;
}