PAT (Advanced Level)-1004. Counting Leaves (30)

PAT (Advanced Level)-1004. Counting Leaves (30)

1004. Counting Leaves (30)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.


Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.

Sample Input

2 1
01 1 02

Sample Output

0 1

解读

题目条件无非就是构建并存储树,但是如何处理题目中输入的父节点和子节点是一个算法中的关键。

采用map容器,把每一个节点和存储它的子节点容器进行关联,可以方便操作。

对于存储之后的统计每层级的叶子数,可以采用深度优先的算法,通过临时变量level,在迭代中不干扰其他支线的统计,保证同级的叶子最终均会统计入LeavesOfLevel数组中。

但是这样做会有一个麻烦,由于迭代的过程level在不同的环节是不同的值,无法直接知晓探索到最深时候level的值,所以我们通过辅助统计的变量LeavesCount记录每一级的叶子数,并在输出时候进行累加,直到LeavesCount与总叶子数Leaves相同,即可停止对LeavesOfLevel数组的输出。

完整代码

#include<iostream>
#include<vector>
#include<map>

using namespace std;

map<int, vector<int>> List;

void DFS(int, int, int[]);

int main()
{
	int N, M;
	int LeavesOfLevel[101] = { 0 };//统计每级上面的叶子节点

	//输入部分
	cin >> N >> M;	
	for (int i = 0; i < M; i++)
	{
		int ID, K, ID_Son;
		cin >> ID >> K;
		for (int j = 0; j < K; j++)
		{
			cin >> ID_Son;
			List[ID].push_back(ID_Son);
		}
	}

	int Leaves = N - M;//统计总叶子数
	//深度优先搜索
	DFS(1, 0, LeavesOfLevel);

	//输出部分
	int LeavesCount = LeavesOfLevel[0];//辅助记录
	cout << LeavesOfLevel[0];
	for (int i = 1; LeavesCount < Leaves; i++)
	{
		cout << " " << LeavesOfLevel[i];
		LeavesCount += LeavesOfLevel[i];
	}
	
	return 0;
}

//深度优先,统计每层级的叶子数
void DFS(int id, int level,int LeavesOfLevel[])
{
	if (List[id].empty())
	{
		LeavesOfLevel[level]++;
		return;
	}

	vector<int>::iterator item = List[id].begin();

	for (; item != List[id].end(); item++)
	{
		DFS(*item, level+1, LeavesOfLevel);
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注