题目粗心:

输出树结点的个数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;}