PAT 甲级 A1094 The Largest Generation

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, K (>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 01. 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 18

Sample Output:

9 4

题意：

告诉你有n个结点，其中有m个非叶子结点，然后给出非叶子结点该结点的编号，子结点个数和子节点的编号，要我们输出该树层数内结点最多的结点个数和该层的层数编号（根结点和层数都是从1开始编号）。

思路：
        因为给出的是编号和结点的关系，因此应该用静态建树比较方便，因为没有权重，所以就不用建造结构体了，直接用vector能放映父结点和子结点的关系就好了。

可以用DFS来做这个题目，递归有两个参数根节点root和层次level，同层次的就用hashtable计数，最后面再遍历找出那个层次的结点最多就好了。

也可以用BFS来做，但要多一个数组存储该结点所在的层次。

代码：

DFS:
 

//编号和结点关系->静态建树，没有权值，不用结构体，直接用一个vector数组; 
#include<iostream>
#include<vector>
using namespace std;
const int maxn=	110;
int hashtable[maxn]={0};//为第i层的结点数计数；
int n,m,father,child,k; 
vector<int > Node[maxn];

void DFS(int root,int level){
	hashtable[level]++;
	if(Node[root].size()==0)return ;
	for(int i=0;i<Node[root].size();i++){
		DFS(Node[root][i],level+1);
	} 
} 

int main( ){
	scanf("%d %d",&n,&m);//结点个数，非叶子结点个数;
	for(int i=0;i<m;i++){
		scanf("%d %d",&father,&k);
		for(int j=0;j<k;j++){
			scanf("%d",&child);
			Node[father].push_back(child);
		}
	}
	DFS(1,1);//根节点编号为1，层次从第1开始编号；
	int maxnum=0,maxlevel=1; 
	for(int i=1;i<maxn;i++){ 
		if(maxnum<hashtable[i]){
			maxnum=hashtable[i];
			maxlevel=i; 
		}
	}
	printf("%d %d",maxnum,maxlevel);
	return 0; 
}

BFS:

//编号和结点关系->静态建树，没有权值，不用结构体，直接用一个vector数组; 
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int maxn=	110;
int hashtable[maxn]={0};//为第i层的结点数计数；
int nodelevel[maxn]={0};//让子结点都在同一层; 
int n,m,father,child,k; 
vector<int > Node[maxn];


void BFS(int root,int level){
	queue<int > q;
	q.push(root);
	nodelevel [level]=1;//根节点的层次; 
	
	while(!q.empty()){
		int top=q.front( );
		q.pop( );
		hashtable[ nodelevel[top] ]++;//该结点所在的层次结点数目+1； 
		for(int i=0;i<Node[top].size();i++){
			nodelevel[Node[top][i]] = nodelevel[top]+1;//遍历top的子节点，结点的层数是top所在层数+1; 
			q.push(Node[top][i]);//其子结点放入队列; 
		}
	}
	
	return ;
} 


int main( ){
	scanf("%d %d",&n,&m);//结点个数，非叶子结点个数;
	for(int i=0;i<m;i++){
		scanf("%d %d",&father,&k);
		for(int j=0;j<k;j++){
			scanf("%d",&child);
			Node[father].push_back(child);
		}
	}
	BFS(1,1);//根节点编号为1，层次从第1开始编号；
	int maxnum=0,maxlevel=1; 
	for(int i=1;i<maxn;i++){ 
		if(maxnum<hashtable[i]){
			maxnum=hashtable[i];
			maxlevel=i; 
		}
	}
	printf("%d %d",maxnum,maxlevel);
	return 0; 
}