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
AC参考代码:
#include <iostream>
#include <vector>
#include <map>
#include <fstream>
using namespace std;
map< int,vector<int> > myTree; //用链式结构来实现多叉树的数据结构
int leafRecord[101] = {0}; //用record数组来实现每一层叶子结点的计数
void DFS(int start,int level)
{
if(myTree[start].empty()){ //临界情况判断
leafRecord[level]++;
return;
}
vector<int>::iterator ite; //用迭代期 遍历子节点
for(ite=myTree[start].begin();ite!=myTree[start].end();ite++){
DFS(*ite,level+1);
}
}
int main()
{
//ifstream cin("1.txt");
int N,M,head,num,index,leafNum;
cin>>N>>M;
leafNum = N-M;
for(int i=0;i<M;i++){
cin>>head>>num;
for(int j=0;j<num;j++){
cin>>index;
myTree[head].push_back(index);
}
}
DFS(1,0);
int leafCnt = leafRecord[0];
//cout<<leafCnt<<endl;
for(int i=1;leafCnt<=leafNum;i++){
leafCnt!=leafNum?printf("%d ",leafRecord[i-1]):printf("%d",leafRecord[i-1]);
if(leafCnt == leafNum) break; //这边需对边界进行判断退出
leafCnt += leafRecord[i];
}
return 0;
}
本题主要是利用深度遍历实现每个层次上的叶子节点的计数;
这边利用map+vector实现多叉树的链式数据结构
题目中的隐含条件leafRecord中的节点数刚好等于N-M实现最后的遍历
水水过了!!
分享到:
相关推荐
1. Basic counting principle 3. Combinations: Binomial coefficient 二项系数 4. Binomi
A family hierarchy等级 is usually presented by a pedigree tree系谱树. Your job is to count those family members who have no child.
To reflect that, and to make the Counting Practices Manual (CPM) even more attractive as a reference manual, the Counting Practices Committee (CPC) decided to restructure CPM 4.2 into four parts: ...
To reflect that, and to make the Counting Practices Manual (CPM) even more attractive as a reference manual, the Counting Practices Committee (CPC) decided to restructure CPM 4.2 into four parts: ...
The Function Point Counting Practices Manual is the definitive description of the Function Pointing Counting Standard. Several versions of the manual are available, each describing the standard or ...
代码行的统计工具,非常好用认识多种语言的源代码,比如java,VB,c++等等。指定文件后可以计算出代码行数,注释行数。
335 5.1 The Basics of Counting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 5.2 The Pigeonhole Principle. . . . . . . . . . . . . ....
论文Attentional Neural Fields for Crowd Counting,侵删
利用差分盒计数法计算图像分维数,利用matlab语言编写
Function Point Counting Practices Manual 4.1.1 版本。 来自IFPUG,权威资料 The primary objectives of the IFPUG Counting Practices Manual, Release 4.1, are to • Provide a clear and detailed description...
poj 2386 Lake Counting.md
Zhang_Cross-Scene_Crowd_Counting_2015_CVPR_paper.pdf
计算1D 2D 3D的分形盒维数。 分形维数被誉为大自然的几何学的分形(Fractal)理论,是现代数学的一个新分支,但其本质却是一种新的世界观和方法论
var countingSort = require ( './countingSort.js' ) ; // Construct input [0, 5], therefore an array of size 6 is needed // for the temporary storage space. var input = [ 2 , 5 , 3 , 0 , 2 , 3 , 0 , 3 ...
PeopleCounting-master.rar
Visdrone2021_CrowdCounting.rar
To reflect that, and to make the Counting Practices Manual (CPM) even more attractive as a reference manual, the Counting Practices Committee (CPC) decided to restructure CPM 4.2 into four parts: ...
These practices are a compilation of acceptable proce- dures for cycle-counting methods employed in fatigue analysis. This standard does not intend to recommend a particular method.
对固定镜头下视频序列中运动人体的检测和跟踪方法进行研究,利用灰度图像差分双向投影信息检测人体目标,提出一种基于统 计运动区域几何特征固定比例的分割算法,使用最近邻匹配方法对人体进行跟踪。