1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805372601090048
输入树的结点个数N（结点编号为1~N），非叶子结点个数M，然后输入M个非叶子结点各自的孩子结点编号，求结点个数最多的一层（层号是从整体来看的，根结点层号为1），输出该层的结点个数和层号（从根结点的第一层开始往下计算）。
2.思路
基础题。
这类题也是直接DFS，不是像上次的【1079】&【1090】供应树DFS一样是到了叶子结点就进行“更新/结算”类型，这题直接利用DFS统计每层的结点个数即可。
3.完整代码
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<vector> using namespace std; const int maxn=110; int parent,sonnum; vector<int>child[maxn]; //int high[maxn]={0};//high[i]为第i层（从上往下）的结点个数 vector<int>high(maxn);//vector容器定义默认元素初值为0 void DFS(int index,int level){ high[level]++; for(int i=0;i<child[index].size();i++){ DFS(child[index][i],level+1);//注意[index]和[i]直接没"." } } int main(){ int leaf,nonleaf; scanf("%d%d",&leaf,&nonleaf); for(int i=0;i<nonleaf;i++){ scanf("%d%d",&parent,&sonnum); for(int j=0;j<sonnum;j++){ int son; scanf("%d",&son); child[parent].push_back(son); } } DFS(1,1);//题目规定根结点为1号结点,注意第二个参数为1(表示层数为1) //下标比较哪层的结点个数最多 int max=0,maxhigh=0; //for(int i=0;i<maxn;i++){//遍历high数组 for(int i=0;i<high.size();i++){//遍历high数组 if(high[i]>max){ max=high[i]; maxhigh=i; } } printf("%d %d",max,maxhigh); system("pause"); }
注意
（1）有的题目最后要输出数据后有个换行符（这里没有也没事）。
（2）这题目规定根结点为1号结点,注意第二个参数为1(表示层数为1)。
（3）定义全局的高度数组int high[maxn]={0};//high[i]为第i层（从上往下）的结点个数，其实也可以设为vector型数组vector<int>high(maxn)。
（4）本题的结点数小于100，数值小，不像之前的【1079】&【1090】供应树DFS结点数可达到10的5次方辣么多。
