PAT 甲级 1094 The Largest Generation-白红宇

PAT 甲级 1094 The Largest Generation

阅读量：4963 次

发布时间：2019-06-12

本文共 2305 字，大约阅读时间需要 7 分钟。

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

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

where ID is a two-digit number representing a family member, K ( $>) 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 1321 1 2301 4 03 02 04 0503 3 06 07 0806 2 12 1313 1 2108 2 15 1602 2 09 1011 2 19 2017 1 2205 1 1107 1 1409 1 1710 1 18

Sample Output:

9 4

代码：

#include 
     
      using namespace std;int N, M;int vis[110], num[110];vector
      
        v[110];int depth = -1;void dfs(int root, int step) {    if(v[root].size() == 0) {        depth = max(depth, step);    }    vis[root] = 1;    num[step] ++;    for(int i = 0; i < v[root].size(); i ++) {        if(vis[v[root][i]] == 0) {            dfs(v[root][i], step + 1);        }    }}int main() {    scanf("%d%d", &N, &M);    memset(vis, 0, sizeof(vis));    for(int i = 0; i < M; i ++) {        int id, K, x;        scanf("%d%d", &id, &K);        for(int k = 0; k < K; k ++) {            scanf("%d", &x);            v[id].push_back(x);        }    }    dfs(1, 1);    int temp, ans = INT_MIN;    for(int i = 0; i <= depth; i ++) {        if(num[i] > ans) {            ans = num[i];            temp = i;        }    }    /*for(int i = 1; i <= depth; i ++)        printf("%d ", num[i]);*/    printf("%d %d\n", ans, temp);    //printf("%d\n", depth);    return 0;}

　　dfs

转载于:https://www.cnblogs.com/zlrrrr/p/10391074.html

你可能感兴趣的文章