dfs和bfs都是常用的搜索算法结合PAT1094简单动手分别以dfs和bfs实现树的遍历吧。1094 The Largest Generation (25 分)A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.Input Specification:Each input file contains one test case. Each case starts with two positive integers N (100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:ID K ID[1] ID[2] ... ID[K]whereIDis a two-digit number representing a family member,K(0) is the number of his/her children, followed by a sequence of two-digitIDs of his/her children. For the sake of simplicity, let us fix the rootIDto be01. All the numbers in a line are separated by a space.Output Specification:For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.Sample Input:23 13 21 1 23 01 4 03 02 04 05 03 3 06 07 08 06 2 12 13 13 1 21 08 2 15 16 02 2 09 10 11 2 19 20 17 1 22 05 1 11 07 1 14 09 1 17 10 1 18Sample Output:9 4题目大意给你一棵树让你找出哪一层的节点个数最多输出节点个数和对应的层数。dfs#includecstdio #includeiostream #includevector const int maxn105; vectorint tree[maxn]; int sum[maxn];//记录每一层的节点个数 int n,m; void dfs(int level,int node){ sum[level]; for(int i0;itree[node].size();i){ dfs(level1,tree[node][i]); } } int main() { cinnm; for(int i0;im;i){ int id,num; cinidnum; for(int j0;jnum;j){ int child; cinchild; tree[id].push_back(child); } } dfs(1,1); int maxnum-1,maxlevel-1; for(int i0;imaxn;i){ if(sum[i]maxnum){ maxnumsum[i]; maxleveli; } } coutmaxnum maxlevelendl; return 0; }bfs#includecstdio #includeiostream #includevector #includequeue using namespace std; const int maxn105; vectorint tree[maxn]; int sum[maxn]; int level[maxn]; //记录节点对应的层数 int n,m; void bfs(){ queueint q; q.push(1); level[1]1; while(!q.empty()){ int nodeq.front(); q.pop(); sum[level[node]]; for(int i0;itree[node].size();i){ level[tree[node][i]]level[node]1; q.push(tree[node][i]); } } } int main() { cinnm; for(int i0;im;i){ int id,num; cinidnum; for(int j0;jnum;j){ int child; cinchild; tree[id].push_back(child); } } bfs(); int maxnum-1,maxlevel-1; for(int i0;imaxn;i){ if(sum[i]maxnum){ maxnumsum[i]; maxleveli; } } coutmaxnum maxlevelendl; return 0; }