题目粗心:
输出树结点的个数N,非叶结点个数M,而后输出M个非叶节点的孩子结点,求结点个数最多的那层,输入该层的结点个数和层号.
算法思路:
此题也是考查树的遍历,能够应用先序遍历或者层序遍历建设每一层和节点个数的关系,这里采纳了层序遍历,间接在出队节点的时候就先更新以后层的节点个数,而后更新最多节点数目和层数。对应代码如下:
int largestGeneration = -1;// 最多节点数目int largestGenerationOfLevel;// largestGeneration对应的层数void levelTraverse(int root){ int levelNum[105] = {};//每一层的节点数目,肯定要初始化 queue<int> q; node[root].level = 1;// 第一层 q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); ++levelNum[node[t].level]; if(largestGeneration<levelNum[node[t].level]){ largestGeneration = levelNum[node[t].level]; largestGenerationOfLevel = node[t].level; } for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } }}
提交后果:
AC代码:
#include <cstdio>#include <vector>#include <queue>using namespace std;struct Node{ vector<int> child; int level;}node[1000];int largestGeneration = -1;// 最多节点数目int largestGenerationOfLevel;// largestGeneration对应的层数void levelTraverse(int root){ int levelNum[105] = {};//每一层的节点数目,肯定要初始化 queue<int> q; node[root].level = 1;// 第一层 q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); ++levelNum[node[t].level]; if(largestGeneration<levelNum[node[t].level]){ largestGeneration = levelNum[node[t].level]; largestGenerationOfLevel = node[t].level; } for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } }}int main(){ int N,M;//供应链总人数 scanf("%d %d",&N,&M); int ID,K; for (int i = 0; i < M; ++i) { scanf("%d %d",&ID,&K); int child; for (int j = 0; j < K; ++j) { scanf("%d",&child); node[ID].child.push_back(child); } } levelTraverse(1); printf("%d %d",largestGeneration,largestGenerationOfLevel); return 0;}