关于算法-数据结构:PAT甲级1094-The-Largest-Generation

题目粗心：

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