PAT (Advanced Level) Practice 1094 The Largest Generation (25 分) 淩宸1642

題目描述：

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]

where

ID

is a two-digit number representing a family member,

(>0) is the number of his/her children, followed by a sequence of two-digit

ID

's of his/her children. For the sake of simplicity, let us fix the root

ID

to be

. All the numbers in a line are separated by a space.

譯：每個輸入檔案包含一個測試。每個用例開始為兩個正整數，代表在家譜樹中的成員結點的總數 N (<100)（是以所有結點按照 01 到 N 進行編号），表示擁有孩子的家族成員的個數 M (<N) 。接下來 M 行有如下的格式，包含一個家庭成員的資訊：

ID K ID[1] ID[2] ... ID[K]

ID

是一個2位數，表示成員的編号,

(>0) 表示其孩子的個數 , 接下來是其孩子結點的編号

ID

序列。為了簡單起見，我們規定根結點的

ID

為

。所有處于同一行的數字之間都用空格隔開。

Output Specification:

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 18

Sample Output (樣例輸出):

9 4

The Idea：

建樹，由于N的範圍很小，可以直接使用結構體來表示節點。
找到根節點，本題固定為 01 。
進行層序周遊，與最基礎的層序周遊不同，這裡還需要填充每個結點的層數，是以在孩子結點入隊之前，可以将其層數值修改為父結點的層數值 + 1。然後再判斷每一層的人數時，我采用了一個表示現在位于哪一層的标志 nowP ，當 nowP 與目前隊首元素結點的level值不一樣時，說明此時是該層的第一個元素，是以這一層的人數值為此時隊列的大小值 q.size() + 1
得到該層人數之後，與最大人數的那一層進行比較，決定是否更新。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
struct NODE{
	int level ;
	vector<int> child;
}Node[100] ;

int n , m , k , id , t ; /
int maxP = 1 , maxG = 1 ;
void levelOrder(int root){
	queue<int> q ;
	q.push(root) ;
	int nowP = 0 , nowG = 1 ;
	while(!q.empty()){
		int top = q.front() ;
		q.pop() ;
		if(Node[top].level != nowG){
			nowG ++ ; // 進入下一層
			nowP = 1 + q.size() ; // 本層的總人數
			if(nowP > maxP){  // 判斷是否需要更新
				maxP = nowP ;
				maxG = nowG ;
			}
		}
		for(int i = 0 ; i < Node[top].child.size() ; i ++){
			int t = Node[top].child[i] ;
			q.push(t) ; // 孩子結點入隊
			Node[t].level = Node[top].level + 1 ; // 孩子結點的層值 = 父結點的層值 + 1
		}
	}
} 

int main(){
	cin >> n >> m ;
	for(int i = 0 ; i < m ; i ++){
		cin >> id >> k ;
		for(int j = 0 ; j < k ; j ++){
			cin >> t ;
			Node[id].child.push_back(t) ;
		}
	}
	Node[1].level = 1 ;
	levelOrder(1) ;
	cout << maxP << " " << maxG << endl ;
	return 0 ;
}

PAT (Advanced Level) Practice 1094 The Largest Generation (25 分) 淩宸1642