題干：

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

題目大意：

給你一棵樹(shù)，讓你找到節(jié)點(diǎn)數(shù)最多的那個(gè)深度和對(duì)應(yīng)的節(jié)點(diǎn)個(gè)數(shù)。

解題報(bào)告：

? 按照題意建樹(shù)，然后dfs掃一遍得到深度，輸出結(jié)果即可。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m; int dep[MAX],cnt[MAX],mx,ans,ansd; vector<int> vv[MAX]; void dfs(int cur,int fa) {dep[cur] = dep[fa] + 1;cnt[dep[cur]]++;mx = max(mx,dep[cur]);int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];dfs(v,cur);} } int main() {cin>>n>>m;for(int fa,num,i = 1; i<=m; i++) {scanf("%d%d",&fa,&num);for(int x,j = 1; j<=num; j++) {scanf("%d",&x);vv[fa].pb(x);}}dfs(1,0);for(int i = 1; i<=mx; i++) {if(cnt[i] > ans) {ansd = i;ans = cnt[i];}}printf("%d %d\n",ans,ansd);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【PAT - 甲级1094】The Largest Generation (25分)（dfs建树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。