`
249326109
  • 浏览: 56062 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

pat 1004. Counting Leaves (30)

 
阅读更多

链接: http://pat.zju.edu.cn/contests/pat-a-practise/1004

 

题意:统计一颗给定树的每层的叶子节点数目。

 

 

分析:基于节点数据量比较小,可以简单地利用链接矩阵的方式存储树,然后利用dfs遍历,遍历的时候记录深度变量用于统计。

 

 

#include<stdio.h>

int mat[105][105];
int num[105];
int n, m;
int maxDep = -1;

void dfs(int id, int dep) {

	int isLeaf = 1;
	int i;
	for (i = 1; i <= n; i++) {
		if (mat[id][i]) {
			isLeaf = 0;
			dfs(i, dep + 1);
		}

	}

	if (isLeaf) {
		num[dep]++;
		if (dep > maxDep)
			maxDep = dep;
	}

}

int main() {
	scanf("%d%d", &n, &m);

	int i;
	for (i = 0; i < m; i++) {
		int father, k, child;
		scanf("%d%d", &father, &k);
		int j;
		for (j = 0; j < k; j++) {
			scanf("%d", &child);
			mat[father][child] = 1;
		}
	}

	dfs(1, 0);

	for (i = 0; i <= maxDep; i++) {
		printf("%d", num[i]);
		if (i != maxDep)
			printf(" ");
	}

	return 0;
}

 

分享到:
评论

相关推荐

    1004. Counting Leaves (30)

    1004. Counting Leaves (30) 来自:http://blog.csdn.net/sunbaigui/article/details/8657008

    takeuchi-kou#bioinfo-study-notes#L04. Counting(排列组合_二项概率_多项概率)1

    1. Basic counting principle 3. Combinations: Binomial coefficient 二项系数 4. Binomi

    Project 2: Counting Leaves

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

    Counting.exe

    《代码行统计工具Counting.exe详解》 在软件开发过程中,了解代码的规模是至关重要的。这不仅可以评估项目的复杂性,还可以为项目管理和资源分配提供参考。Counting.exe是一款高效实用的代码行统计工具,它支持多种...

    [iFPUG] Function Point Counting Practices Manual R4.2.1-2005.pdf

    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: ...

    Function Point Counting Practices Manual4.2.1

    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: ...

    PAT甲级真题练习1

    4. Counting Leaves (30) Counting Leaves是一个中等难度的数据结构题,要求考生编写一个程序来统计树叶的数量。该题目考察了考生的数据结构设计能力和算法设计能力。 知识点: * 树形数据结构 * 遍历算法 * 统计...

    53958727box-counting.zip

    本项目"53958727box-counting.zip"显然是针对1D、2D、3D空间中分形维数的计算,旨在理解和探索不同维度下的分形特性。 分形维数,作为一个概念,是由曼德勃罗集的创始人Benoit Mandelbrot引入的,它超越了传统...

    differential-box--counting.rar_box counting fractal_matlab计数_差分盒

    差分盒计数法(Differential Box Counting,简称DBC)是一种通过统计不同大小的“盒子”覆盖图像中点的数量来估计分形维数的方法。分形维数是一个无量纲的数值,它描述了对象在不同尺度下的复杂性。在图像处理中,这...

    271760513/pinpoint:2.3.3 pinpoint 探针使用

    pinpoint 探针,docker镜像 271760513/pinpoint:2.3.3 使用

    counting 代码行数统计

    4. **Counting.dsp**:这是Visual Studio的项目文件,用于构建和管理整个代码行统计工具的源代码。 5. **ReadMe2.txt**:通常包含关于如何使用、安装或配置项目的说明。 6. **CreditStatic.CPP**:可能是用于显示...

    box_count.zip_box_box counting _box-counting

    Box Counting方法是一种在复杂系统和分形几何中计算维度的数学技术,它主要用于分析和理解数据集或图像的自相似性。这个压缩包“box_count.zip”包含了用于执行Box Counting算法的MATLAB代码,这有助于计算一个系统...

    【C++】PAT甲级题目实现

    为了记录我在准备PAT甲级的练习,特开此页。...Counting Leaves https://blog.csdn.net/weixin_42426496/article/details/104222455 1006 Sign In and Sign Out https://blog.csdn.net/weixin_42426496/article/detai

    [离散数学及其应用(英文第六版)].Discrete.Mathematics.and.its.Applications.djvu

    335 5.1 The Basics of Counting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 5.2 The Pigeonhole Principle. . . . . . . . . . . . . ....

    Attentional Neural Fields for Crowd Counting.pdf

    论文Attentional Neural Fields for Crowd Counting,侵删

    poj 2386 Lake Counting.md

    poj 2386 Lake Counting.md

    Function Point Counting Practices Manual.zip

    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...

    source统计工具Counting

    使用Counting.exe这个执行文件,用户只需指定要分析的源代码目录,工具就会自动生成统计报告。这些报告通常会以清晰易读的格式展示,如CSV或HTML,方便用户查看和分析。报告中可能包括每种类型行的计数、文件大小的...

    CountingSort:计数排序算法的实现

    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 ...

Global site tag (gtag.js) - Google Analytics