PAT(AdvancedLevel)PracticeA1094TheLargestGeneration（25分）(C++)（甲级）（树、层次遍历）

原题链接&＃xff1a;A1094 The Largest Generation

#include
#include
#include
#include
#include
using namespace std;typedef struct PTNode
{vector<int> child;
} PTNode;
PTNode PTree[100];
int N, M, K, max_width_level &＃61; 1, max_width &＃61; 1;//最大宽度&＃xff0c;和最大宽度所在层次void BFS(int ID)//广度优先搜索思想&＃xff0c;或者说层次遍历思想
{queue<int> Q;Q.push(ID);int level &＃61; 1, width &＃61; 0, last_ID &＃61; 1;//last_ID记录该行的最后一个while(!Q.empty()){ID &＃61; Q.front();Q.pop();width&＃43;&＃43;;//本行宽度计数for(int i&＃61;0; i<(PTree[ID].child).size(); i&＃43;&＃43;){Q.push(PTree[ID].child[i]);//孩子入队}if(ID &＃61;&＃61; last_ID)//该行结束&＃xff0c;更新层次数、最大宽度和last_ID{last_ID &＃61; Q.back();if(width > max_width){max_width &＃61; width;max_width_level &＃61; level;if(!Q.empty()) last_ID &＃61; Q.back();}level&＃43;&＃43;;width &＃61; 0;}}
}int main()
{scanf("%d %d", &N, &M);for(int i&＃61;0, ID, child_id; i<M; i&＃43;&＃43;){scanf("%d %d", &ID, &K);for(int j&＃61;0; j<K; j&＃43;&＃43;){scanf("%d", &child_id);(PTree[ID].child).push_back(child_id);}}BFS(1);//层次遍历printf("%d %d", max_width, max_width_level);return 0;
}