pat-1004* Counting Leaves

1004: 统计树的每一层上叶子节点的个数

Sample Input
2 1
01 1 02
Sample Output
0 1

用二维数组存了树，dfs搜索了一下。最左一列统计节点孩子数量，最上一行用于记录每层叶子数。

#include<iostream>
using namespace std;
#include<string.h>
#include<memory.h>

int tree[101][101];
int maxlevel=0;

void travel(int root,int level)
{
	if(level>maxlevel)
		maxlevel = level;
	if(tree[root][0]==0)
		tree[0][level]++;
	else
	{
		for(int i=1;i<101;i++)
		{
			if(tree[root][i]==1)
				travel(i,level+1);
		}
	}
}

int main()
{
	int total;
	int nonleave;
	int parent;
	int child;
	int childnum;

	memset(tree,0,sizeof(tree));
	cin>>total;
	cin>>nonleave;
	for(int i=0;i<nonleave;i++)
	{
		cin>>parent;
		cin>>childnum;
		for(int j=0;j<childnum;j++)
		{
			cin>>child;
			tree[parent][child]=1;
			tree[parent][0]++;
		}
	}
	travel(1,0);
	for(int i=0;i<=maxlevel;i++)
	{
		cout<<tree[0][i];
		if(i!=maxlevel)
			cout<<" ";
	}

}