[PAT解题报告] Counting Leaves
给定一个树，求每层没有孩子的节点数。首先，树是邻接表的形式给的，即每个节点的孩子有哪些。其次，这个树是有根树。注意：节点数0
< N < 100, 但题目好像没说节点id是连续的，尽管都小于100。所以我没有假设节点id连续，读入的节点数n，我也没有用。
不过我假设了每个写出的节点id, k 后面跟k个孩子，而k不应该等于0，确实题目没说k != 0这个问题……
两种办法解决这个问题：
第一种方法对每个节点记录一个父亲f值，然后标记该节点是否有孩子hasSon[i]——我们不应该用度是否为1来判断叶子，因为只有两个节点的时候，根不能算做叶子。然后根据f值计算每个节点的深度dep，
一般dep[i] = dep[f[i]] + 1，
这个可以dfs出来。我还记录了每个编号的节点是否存在mark[],有了这些信息之后，如果节点i深度为
i并且没有孩子，我们就把它的深度加到最终答案上就好了，++a[dep[i]]。当然还要记录树的高度max{dep[i]}，最后输出就行了。这个做法有个细节，当n
= 1, m =
0时，这个树是个孤立点，我们根据读入的信息，无法记录mark值，也就是说我们会认为这个树没有节点，这种情况应该输出1——记得要特判一下，有点不美观。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
using namespace std;
const int N = 102;
bool mark[N];
int dep[N];
int f[N];
bool haveSon[N];
int a[N];
int getDep(int x) {
return ((!mark[x]) || (f[x] < 0))?0:(1 + getDep(f[x]));
}
int main() {
int n, m;
scanf("%d%d",&n,&m);
if (m == 0) {
puts("1");
return 0;
}
for (memset(f, 0xff, sizeof(f));m;--m) {
int x,y;
for (scanf("%d%d",&x,&y);y;--y) {
int z;
scanf("%d",&z);
mark[z] = true;
f[z] = x;
}
mark[x] = haveSon[x] = true;
}
n = 0;
for (int i = 0; i < N; ++i) {
if (mark[i]) {
dep[i] = getDep(i);
if (!haveSon[i]) {
++a[dep[i]];
}
n = max(n, dep[i]);
}
}
for (int i = 0; i <= n; ++i) {
if (i) {
putchar(' ');
}
printf("%d",a[i]);
}
puts("");
return 0;
}
第二种方法是稍微麻烦一点，我们同样用mark[]记录节点是否出现，并且用canRoot[]表示这个节点是否可能是根(没有父亲）。根据读入的信息，我们更新mark,
canRoot——这和前面差不多，并且我们用vector<int>
son[]存放每个节点的孩子们，也就是读进来直接扔到vector里面去。然后，我们找到树根也就是canRoot[r] == true
&& mark[r] == true的点——如果找不到r = 0，这就是我说的n = 1, m =
0的特殊情况。接下来我们对树从根开始做层序遍历，也就是bfs。bfs时用两个队列来回折腾的方法——先从一个队列1出队，把那些孩子全放入队列2。队列1清空后，从队列2出队，把孩子放入队列1……这样每个队列负责一层，而且只有两个队列。实现这个的方法我们用两个变量表示队列编号就好了。比如last
= 0, now = 1 ^ last。每次循环后last ^= 1就好了，实际上last就是0，1，0，1，0，1这样的，now正好是1
- last。我们遍历完一层就能统计没有孩子的节点数了，因为没有孩子的节点son[x].empty() == true。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N = 102;
bool canRoot[N];
bool mark[N];
vector<int> son[N];
queue<int> q[2];
int main() {
int n, m;
for (int i = 0; i < N; ++i) {
canRoot[i] = true;
}
for (scanf("%d%d",&n,&m);m;--m) {
int x,y;
for (scanf("%d%d",&x,&y);y;--y) {
int z;
scanf("%d",&z);
mark[z] = true;
canRoot[z] = false;
son[x].push_back(z);
}
mark[x] = true;
}
int r = 0;
for (int i = 0; i < N; ++i) {
if (mark[i] && canRoot[i]) {
r = i;
break;
}
}
q[0].push(r);
bool first = true;
for (int last = 0;!q[last].empty();last ^= 1) {
int answer = 0;
int now = last ^ 1;
while (!q[last].empty()) {
int x = q[last].front();
q[last].pop();
if (son[x].empty()) {
++answer;
}
else {
for (int i = 0; i < son[x].size(); ++i) {
q[now].push(son[x][i]);
}
}
}
if (first) {
first = false;
}
else {
putchar(' ');
}
printf("%d",answer);
}
puts("");
return 0;
}
题目链接： http://www.patest.cn/contests/pat-a-practise/1004
