[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