AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 1584. 最大的一代    原题链接    简单

作者: 作者的头像   TracyGeorge ,  2021-02-23 17:56:55 ,  阅读 19


0


1.因为子节点的高度是父节点高度+1,所以在bfs所有节点的同时,可以更新最大个数,和其对应的层数。
2.储存方式是邻接表
#include<iostream>
#include<vector>
#include<string.h>
#define N 110
using namespace std;
int e[N],ne[N],h[N],cnt[N];
int idx=0,n,m,id,k,son,max_cnt=0,max_level=0;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int root,int level){
    cnt[level]++;
    if(max_cnt<cnt[level]) max_cnt=cnt[level],  max_level=level;
    for(int i=h[root];i!=-1;i=ne[i]) dfs(e[i],level+1); 
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d %d",&n,&m);
    while(m--){
        scanf("%d %d",&id,&k);
        while(k--){
            scanf("%d",&son);
            add(id,son);
        }
    }
    dfs(1,1);
    printf("%d %d",max_cnt,max_level);
}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息