[PAT解题报告] The Largest Generation
简单题，给定一棵树——树是按照父子关系给出的，求节点个数最多的那层有多少个节点——保证这层是唯一的。并且认为根的层数为1。
因为数非空，并且规定了根是1号，我把id都减去1之后，就认为第0层是根。用d[]表示每个节点的层数，即深度。用num[]表示每层的节点数。别忘记初值d[0]
= 1, num[1] = 1。
读入树结构的时候，我们记录每个节点x的父亲y，即f[x] = y。 则d[x] = d[y] +
1。我们dfs求出每个节点的深度——注意如果之前求过，递归可以直接返回，所以计算深度是O(n)的，相当于dfs整个树。我用了全局变量，没求过的深度暂且认为0。当然也可以从根直接dfs一次直接得到每个节点的深度，写起来比我现在这个稍微麻烦一点，总之可以求出每个节点的深度，顺便累加到num[d[x]]上面去，就能求出节点数最多的层了。
代码；
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int f[105];
int d[105] = {1};
int num[105] = {0, 1};
int getd(int i) {
return d[i]?d[i]:(d[i] = getd(f[i]) + 1);
}
int main() {
int n, m;
for (scanf("%d%d", &n,&m);m;--m) {
int x, i;
scanf("%d%d",&x,&i);
for (--x; i; --i) {
int y;
scanf("%d", &y);
f[y - 1] = x;
}
}
m = 1;
for (int i = 1; i < n; ++i) {
int temp = getd(i);
if (++num[temp] > num[m]) {
m = temp;
}
}
printf("%d %d\n", num[m], m);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1094
查看20道真题和解析