(PAT 1094) The Largest Generation (树的层序遍历)

你的名字 2022-03-20 16:50 94阅读 0赞

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

解题思路:

利用队列层序遍历树即可,保留层号

我的算法会忽略最后一层的情况导致出错,所以在层序遍历结束后还要再判断一次

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    int N, M;
    struct Mnode {
    	vector<int> childs;
    }MTree[110];
    int largetLayer = 1;
    int largePopulations = 1;
    void BFS_T(int nroot) {
    	queue<int> bfs_queue, layer_queue;
    	bfs_queue.push(nroot);
    	layer_queue.push(1);   //从1层开始
    	int basicLayer = 1;
    	int basicpop = 0;
    	while (!bfs_queue.empty()) {
    		int vertex = bfs_queue.front();
    		int curlayer = layer_queue.front();
    		bfs_queue.pop();
    		layer_queue.pop();
    		if (curlayer != basicLayer) {   //忽略了最后一层
    			if (basicpop > largePopulations) {
    				largePopulations = basicpop;
    				largetLayer = basicLayer;
    			}
    			basicpop = 1;
    			basicLayer = curlayer;
    		}
    		else {
    			basicpop++;
    		}
    		for (auto tchild : MTree[vertex].childs) {
    			bfs_queue.push(tchild);
    			layer_queue.push(curlayer + 1);
    		}
    	}
        //最后一层也要加以判断
    	if (basicpop > largePopulations) {
    		largePopulations = basicpop;
    		largetLayer = basicLayer;
    	}
    }
    
    int main() {
    	scanf("%d %d", &N, &M);
    	int num, tempRoot, tempchild;
    	for (int i = 0; i < M; ++i) {
    		scanf("%d %d", &tempRoot, &num);
    		for (int j = 0; j < num; ++j) {
    			scanf("%d", &tempchild);
    			MTree[tempRoot].childs.push_back(tempchild);
    		}
    	}
    	BFS_T(1);
    	printf("%d %d", largePopulations, largetLayer);
    
    	system("PAUSE");
    	return 0;
    }