[pat题解]1004.Counting Leaves

pat 1004题。
每个家族结构通常表示为一棵家谱树,家谱树种每一带偶尔会有一些人没有后代。也就是树种每一层偶尔会有无子节点的情况。
题目给定一个家谱树,要求统计每一代,也就是树中每一层有多少个节点没有子节点。
家谱树的输入为按标号输入,输入某个节点,然后后面跟着其所有子节点,一次类推。

做法是逐层遍历,累死与层序遍历,统计每一层中的无子节点的节点个数即可,即每层的叶子节点个数,记录层的方法很多种,这里直接使用两个vector记录当前层和下一层中的节点,依次按层遍历。

c++代码如下:

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

using namespace std;

map<int, vector<int>> trees;
vector<int> res;

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int p, k, son;
		cin >> p;
		cin >> k;
		for (int j = 0; j < k; ++j)
		{
			cin >> son;
			trees[p].push_back(son);
		}
	}

	vector<int> cur;
	vector<int> next = { 1 };
	int idx = 0;
	while (!next.empty())
	{
		res.push_back(0);
		swap(cur, next);
		next.clear();

		for (auto ite = cur.begin(); ite != cur.end(); ++ite)
		{
			if (trees[*ite].empty())
			{
				++res[idx];
				continue;
			}
			vector<int> &sons = trees[*ite];
			for (auto s = sons.begin(); s != sons.end(); ++s)
			{
				next.push_back(*s);
			}
		}
		++idx;
	}
	int nlevels = res.size();
	for (int i = 0; i < nlevels; ++i)
	{
		cout << res[i];
		if (i != nlevels - 1)cout << " ";
	}
	cout << endl;
	return 0;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[pat题解]1004.Counting Leaves

本文链接地址:http://www.iaccepted.net/algorithm/pat/64.html

相关文章



发表评论

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