PAT A1004

还是数层数和数节点的问题，个人觉得用BFS比较好；当然用DFS也能做，具体的思路就是建立层数数组，深度遍历到x层的时候，如果是叶子节点就leaf[x]++，如果不是就不管，继续跳过；代码片段可以这样：void DFS(int index,int h){ max_h=max(h,max_h); if(G[index].size()==0){ leaf[h]++; return; } for(int i=0;i<G[index].size();i++){ DFS(G[index][i],h+1); }}BFS代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<queue>using namespace std;using std::vector;using std::queue;const int maxn=110;int n,m;int leaf[maxn]={0};//每层leaf个数vector<int> table[maxn];int BFS(int x){ int layer=0; queue<int>q; q.push(x); while(!q.empty()){ int num=0; int length=q.size(); layer++; for(int i=0;i<length;i++){ int id=q.front(); q.pop(); if(table[id].size()==0){ num++; } for(int j=0;j<table[id].size();j++){ q.push(table[id][j]); } } leaf[layer]=num; } return layer;}int main(){ int root,l,num; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d %d",&root,&num); for(int j=0;j<num;j++){ scanf("%d",&l); table[root].push_back(l); } } int layer=BFS(1); for(int i=1;i<=layer;i++){ if(i==1) printf("%d",leaf[i]); else printf(" %d",leaf[i]); } system(“pause”); return 0;}