pta甲级1004，DFS算法（题目，翻译，详解）_pta 1004

1004.计算叶子个数

一个家庭的层级结构经常被表现为一个家谱树。你的任务是统计这些家庭成员中谁没有孩子。

输入

每个输入文件包含一个测试实例。每个实例开始的一行包含N和M，N指树中的结点个数（0<N<100），M指非叶结点的个数。然后下面有M行，每行的格式如下：

ID K ID[1] ID[2] ...ID[K]

ID是一个两位数的数字，表示一个非叶结点。K表示其孩子的数量。随后是一个序列，序列中是该结点的孩子结点的两位数ID。为了简单起见，我们把根结点的ID固定为01。

输出

对于每个测试实例，你应该计算从根结点开始的每一层中没有孩子的家庭成员的个数。数字必须在一行内输出，用空格分隔，在每行结尾不能有多余的空格。

测试样例表示了一个只有两个结点的树，01是根结点，02是它仅有的孩子。因此在根结点01层级，没有叶节点。再下一层级，有一个叶结点。然后我们应该在一行内输出“0 1”。

样例输入

2 1

01 1 02

样例输出

0 1

首先需要建立一个树，也就是

const int MAXN=100;

vector<int>tree [MAXN];

行数也就是层数为100，列数也就是每层的节点数不定，这样一个二维数组就可以储存所有的节点了，采用的是孩子表示法，id是节点的编号，i代表的是这个节点的孩子，tree[id][i]的值也是id编号,i从0开始，这样我们就可以通过类似tree [tree[id][i]] [i]的形式来访问某个节点的孩子的孩子了。

欸？如果某个节点没有孩子怎么办？那么tree[id]这个容器就为空喽。

#include<iostream>
#include<vector>
using namespace std;
 
const int MAXN = 100;
vector<int> tree[MAXN];//数组容器
int cnt[MAXN];//记录每一层的叶子节点个数，也就是没有孩子的节点
int sum=0;
 
void dfs(int id, int level)//当前节点编号，
{
	if (tree[id].empty())//如果为空,说明是叶子节点
	{
		cnt[level]++;
		return;
	}
	for (int i = 0; i < tree[id].size(); i++)
	{
		dfs(tree[id][i], level + 1);
	}
}
int main()
{
	int n, m;
	cin >> n >> m;
	int d=m;
	while (m--)
	{
		int id, k;
		cin >> id >> k;
		while (k--)
		{
			int child;
			cin >> child;
			tree[id].push_back(child);
		}
	}
	dfs(1, 0);
	for (int i = 0; i < MAXN; i++)
	{
		cout<<cnt[i];
		sum+=cnt[i];
		if((sum+d)==n)
		{
			break;
		}else cout<<' ';
	}
	cout << endl;
	return 0;
 
 
}