其它综合

PAT甲1004CountingLeaves【dfs】

我爱IT资讯库   2021/02/25
1004counting leaves(30 分)

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 containing0lt;nlt;100, the number of nodes in a tree, andm(lt;n), the number of non-leaf nodes. thenmlines follow, each in the format:

id k id[1] id[2] ... id[k]

whereidis a two-digit number representing a given non-leaf node,kis the number of its children, followed by a sequence of two-digitid‘s of its children. for the sake of simplicity, let us fix the root id to be01.

the input ends withnbeing 0. that case must not be processed.

output specification:

for each test case, you are supposed to count those family members who have no childfor every seniority levelstarting 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, where01is the root and02is its only child. hence on the root01level, there is0leaf node; and on the next level, there is1leaf node. then we should output0 1in a line.

sample input:

2 1
01 1 02

sample output:

0 1

题意:

给定一棵树和节点之间的关系。要求统计每一层的叶子节点个数。

思路:

就建树,暴力dfs就好了。maxn=105的时候wa和re了,改成了1005就过了。

 1 #include lt;iostreamgt;
 2 #include lt;setgt;
 3 #include lt;cmathgt;
 4 #include lt;stdio.hgt;
 5 #include lt;cstringgt;
 6 #include lt;algorithmgt;
 7 #include lt;vectorgt;
 8 #include lt;queuegt;
 9 #include lt;mapgt;
10 #include lt;bits/stdc++.hgt;
11 using namespace std;
12 typedef long long ll;
13 #define inf 0x7f7f7f7f
14 
15 const int maxn = 1005;
16 int n, m;
17 struct node{
18     int v, nxt;
19 }edge[maxn];
20 int head[maxn], tot = 0;
21 int cnt[maxn], dep = -1;
22 
23 void addedge(int u, int v)
24 {
25     edge[tot].v = v;
26     edge[tot].nxt = head[u];
27     head[u] = tot++;
28     edge[tot].v = u;
29     edge[tot].nxt = head[v];
30     head[v] = tot++;
31 }
32 
33 void dfs(int rt, int fa, int h)
34 {
35     int sum = 0;
36     dep = max(dep, h);
37     for(int i = head[rt]; i != -1; i = edge[i].nxt){
38         if(edge[i].v == fa)continue;
39         sum++;
40         dfs(edge[i].v, rt, h + 1);
41     }
42     if(sum == 0){
43         cnt[h]++;
44     }
45 
46 }
47 
48 int main()
49 {
50     scanf("%d%d", amp;n, amp;m);
51     memset(head, -1, sizeof(head));
52     for(int i = 0; i lt; m; i++){
53         int u, k;
54         scanf("%d %d", amp;u, amp;k);
55         for(int j = 0; j lt; k; j++){
56             int v;
57             scanf("%d", amp;v);
58             addedge(u, v);
59         }
60     }
61 
62     dfs(1, -1, 1);
63     //coutlt;lt;deplt;lt;endl;
64     printf("%d", cnt[1]);
65     for(int i = 2; i lt;= dep; i++){
66         printf(" %d", cnt[i]);
67     }
68     printf("\n");
69     return 0;
70 }

pat甲1004 counting leaves【dfs】

原文地址:https://www.cnblogs.com/wyboooo/p/9886333.html




热门内容

171.[LeetCode]Excel Sheet Column Number

题目: Related to question Excel Sheet Column Title ... ...

在.NET中获取一台电脑名,IP地址及当前用户名

在.NET中获取一台电脑名,IP地址及当前用户名是非常简单,以下是我常用的几种方法,如果大家还有其他好的方法,可以回复一... ...
sun directory server

sun directory server

Sun One Directory Server(LDAP)安装和调整指南   ... ...
黑客讲故事:攻下隔壁女生路由器后,我都做了些什么

黑客讲故事:攻下隔壁女生路由器后,我都做了些什么

路由器被蹭网后,我有被黑的风险吗? Evi1m0,来自知道创宇,邪红色信息安全组织创始人 其实这个问题可以... ...

oracle 10g for redhat5

解压文件 解压文件命令: unzip 10201_database_linux32.zip ... ...

什么是I2C协议?

I2C协议是单片机与其它芯片常用的通讯协议,由于只需要两根线,所以很好使用。 一. I2C协议技术性能:&nb... ...

[USACO15DEC]最大流MaxFlow

题目:洛谷p3128。 题目大意:一棵n个点的树,每次将两个节点最短路径所覆盖的所有节点的流量加1。问你最后流量最大的节 ...

kde4.1 alpha1

KDE Project Ships First Alpha of KDE 4.1 KDE Commun... ...

oracle 函数 和 优化

sql语句中,如果where条件里面含有not, !=, <> ,null ,则即使该字段建有索引,也... ...
09年中国互联网企业市值排名

09年中国互联网企业市值排名

这是一个最坏的时代,也是一个最好的时代。自07年底美国次贷危机以来,全球经济发生了巨大的变化。股票市场也随之跌荡起... ...

用于发送UDP消息的SQL Server 扩展存储过程

下载源文件 13.1 kb介绍我希望能够发布 sql server 表更新,因此修改了微软的示例扩展存储过程 xp_he ...

Cache与Fetch(二)

这两天一直百思不得其解的问题终于解决了,这个问题如下: 通过HQL:“select distinct forumGr... ...

[转]小规模低性能低流量网站设计原则

作者: Fenng 网址: http://www.dbanotes.net/arch/small_site... ...

divcss圆角

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transit... ...

Kindle Paperwhite 越狱/加字体/支持PDF、EPUB、DjVu、FB2、CHM和DOC文档

0. 升级 官网固件升级:http://www.amazon.com/gp/help/customer/displ... ...
购物网第二阶段总结笔记3:用户注册模块

购物网第二阶段总结笔记3:用户注册模块

事先工作: 【1】建立用户表:  分析静态页面的用户信息,可以得出用户表所需的字段,建立用户表S... ...

pythonbottleweb框架简介

bottle 是一个快速,简单,轻量级的 python wsgi web 框架。单一文件,只依赖 python 标准库 ...

Android Log介绍

android.util.Log常用的方法有以下5个:Log.v() ,Log.d() ,Log.i() ,Log.w(... ...

target action版简化命令设计模式原理分析

我们知道在Cocoa程序中, 如果你想处理一个窗口的事件或者应用程序的事件, 你可以使用Delegate的方法来实现响应... ...

AHP层次分析法计算权重

一. AHP层次分析法介绍     层次分析法(Analytic Hierarchy... ...

AddingGravitytoyourUIComponents

problem you want your ui components to have gravity, so that ...

我的tmux配置

# General Setting set-option -g prefix C-a ... ...

Android适配器之---SimpleCursorAdapter

结构 继承关系 public class SimpleCusrorAdapter extends Reso... ...

008.不要在该奋斗的年纪选择去偷懒

转载地址:不要在该奋斗的年纪选择去偷懒 不要在该奋斗的年纪选择去偷懒,只有度过了一段连自己都被感动了的... ...

不能读取记录;在MSysObjects上没有读取数据权限-80040E09

当我读取ACCESS里的系统表MSysObjects时,出现:不能读取记录;在 MSysObjects 上没有读取... ...

[Django]bulk_create探究

使用django orm大批量插入的时候我们可以不使用for循环对一个一个的save而是使用 bulk_create ...

不均衡分区和绑定变量窥视导致的查询计划错误

不均衡分区和绑定变量窥视导致的查询计划错误 周一收到生成支持人员的报告,系统上一个作业启动后很长时间没有完成,其执... ...

SQLCookbook学习笔记

许多人以一种马马虎虎的态度在使用sql,根本没有意识到自己掌握着多么强大的武器。本书的目的是打开读者的视野,看看sql究 ...

Android ImageView长按保存图片及截屏相关知识

在日常开发中,可能会需要做长按保存图片这个功能,又或者需要做个截屏分享功能。最近正好在研究这些东... ...

Ruby中的block代码块学习教程

1、什么是代码块 在Ruby中,{}或do...end之间的代码是一个代码块。代码块只能出现在一个方法的后边,它紧接在方... ...