【1004】Counting Leaves (30 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;
const int N=110;
vector<int> G[N]; //存放树
int leaf[N]={0}; //存放每层的叶子结点个数
int max_h=1;  //树的深度
void DFS(int index,int h){ //index为当前遍历到的结点编号 h为当前的深度
  max_h=max(h,max_h); //记录树maxh，便于后面遍历输出每层节点数
  if(G[index].size() == 0){ //如果该结点是叶子结点
    leaf[h]++;
    return;
  }
  for(int i=0;i<G[index].size();i++) { //枚举所有子结点
    DFS(G[index][i],h+1);
  }
}
int main(){   
  int n,m,parent,child,k;
  scanf("%d%d",&n,&m);//结点数 非叶子结点数
  for(int i=0;i<m;i++){
    scanf("%d%d",&parent,&k); //父结点编号及子结点个数
    for(int j=0;j<k;j++){
      scanf("%d",&child); //子结点编号
      G[parent].push_back(child); //加边
    }
  }
  DFS(1,1);//根结点编号为1 及其h=1
  printf("%d",leaf[1]); 
  for(int i=2;i<=max_h;i++)  printf(" %d",leaf[i]);
  system("pause"); 
    return 0;   
}