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] 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
采用层次遍历 两个队列的相互判断即可解决 以下为AC代码
#include <cstdio> #include <algorithm> #include<iostream> #include<vector> #include<cmath> #include<iomanip> #include<map> #include<queue>; using namespace std; class people { public: vector<int> sons; }; people ps[200]; int main() { int N, K; cin >> N >> K; for (int i = 0; i < K; i++) { int no; scanf_s("%d", &no); int sonno; scanf_s("%d", &sonno); for (int j = 0; j < sonno; j++) { int sons; scanf_s("%d", &sons); ps[no].sons.push_back(sons); } } queue<int> tps; int layer = 0; int maxno = 0; tps.push(1); int t = 1; while (!tps.empty()) { queue<int> temp; int lno = 0; while (!tps.empty()) { int nos = tps.front(); tps.pop(); lno++; for (int i = 0; i < ps[nos].sons.size(); i++) { temp.push(ps[nos].sons[i]); } } tps = temp; if (lno > maxno) { maxno = lno; layer = t; } t++; } cout << maxno << " " << layer << '\n'; }