PAT甲级——A1004 Counting Leaves
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0, the number of nodes in a tree, and M (<), 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
.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
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
即遍历整颗数,使用DFS或者DFS
用数组记录每个节点的子节点是谁
#include <iostream>
#include <vector>
#include <queue> using namespace std; //给出一棵树,问每一层的叶子结点数量
//使用BFS或者DFS vector<vector<int>>nodes();
vector<int>depth();
int maxDepth = -; void DFS(int index, int h)
{
maxDepth = maxDepth > h ? maxDepth : h;
if (nodes[index].size() == )//data[index].size() == 0)//即为叶子结点
depth[h]++;//层数 for (int i = ; i < nodes[index].size(); ++i)
DFS(nodes[index][i], h + );
} void BFS( )
{
queue<int>q;
q.push();
vector<int>level(, );//记录节点层数
while (!q.empty())
{
int index = q.front();
q.pop();
maxDepth = maxDepth > level[index] ? maxDepth : level[index];//存储最大的层数
if (nodes[index].size() == )//此节点为叶子节点
depth[level[index]]++;//之所以要记录每个节点的层数,是因为,同一层有多个节点
for (int i = ; i < nodes[index].size(); ++i)
{
level[nodes[index][i]] = level[index] + ;//孩子结点层数比父节点多一层
q.push(nodes[index][i]);//将其孩子全部存入
}
}
} int main()
{
int N, M;//N为节点数目
cin >> N >> M;
for (int i = ; i < M; ++i)
{
int ID, k, a;
cin >> ID >> k;
for (int j = ; j < k; ++j)
{
cin >> a;
nodes[ID].push_back(a);//即为一个节点底下所挂的子节点
}
} //DFS(1,0);
BFS( );
cout << depth[];
for (int i = ; i <= maxDepth; ++i)
cout << " " << depth[i];
cout << endl; return ; }
最新文章
- jsp中两种include的区别【转】
- iOS简易图片选择器 (图片可多选,仿微信)
- HDU 4342History repeat itself 数学
- eclipse创建java类时自动添加注释
- Wince 文本函数和字体应用
- SQL Server tables export/import with bcp
- Adb工具常用操作(一)
- 跟着辛星认识一下PHP的自己主动载入
- Flask Session 使用和源码分析 —— (6)
- Java IO流操作汇总: inputStream 和 outputStream【转】
- find命令配合sed命令使用
- 【ASP.NET MVC系列】浅谈jqGrid 在ASP.NET MVC中增删改查
- 深度残差网络(DRN)ResNet网络原理
- CentOS 解决vim乱码问题
- 使用proxy来简单的实现一个观察者
- 20155323刘威良《网络对抗》Exp8 Web基础
- 在Spark上通过BulkLoad快速将海量数据导入到Hbase
- python5-常用模块
- cogs1685 【NOI2014】魔法森林 Link-Cut Tree
- flow 类型生成工具 flow-typed 简单使用