1004 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
import java.util.* ; public class Main{
static class Node{
int id;
Queue<Node> children;
Node(int id){
this.id=id;
}
}
static HashMap<Integer,Node> tree;
static int N;//树的节点个数
static int M;//有孩子的节点数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
tree = new HashMap<>();
for(int i=;i<M;i++){
int id=sc.nextInt();
int K = sc.nextInt();
Node node = new Node(id);
Queue<Node> children = new LinkedList<>();
for(int j=;j<K;j++){
Node no = new Node(sc.nextInt());
children.offer(no);
}
node.children=children;
tree.put(id,node);
}
Queue<Node> que =new LinkedList<>();
que.add(tree.get());
BFS(que);
} public static void BFS(Queue<Node> que){
int len = ;
Queue<Node> NextQue = new LinkedList<>();
while(que.size()!=){
Node node = que.poll();
if(tree.size()==||!tree.containsKey(node.id)){
len++;
}else{
NextQue.addAll(tree.get(node.id).children);
}
}
if(NextQue.size()==){
System.out.print(len);
}
else {
System.out.print(len+" ");
BFS(NextQue);
}
}
}
思路为BFS。
HashMap建树。
最新文章
- [PHP源码阅读]array_push和array_unshift函数
- 一款基于jQuery日历插件的开发过程
- asp.net mvc短信接口调用——阿里大于API开发心得
- Android滑动菜单特效实现,仿人人客户端侧滑效果,史上最简单的侧滑实现
- Sublime Text3 以及 SublimeREPL使用Virtualenv执行python
- (四)SQL入门 数据库的操作与事务管理
- 【uTenux实验】任务管理
- 复制表结构和数据SQL语句
- [转]瓦的VPS后台kiwivm面板使用+安装AMH+装VPN
- 【转】Java中Vector和ArrayList的区别
- 转:MFC中创建多线程
- cocos2d-x多分辨率和随后的自适应CCListView的bug修复
- js的异步加载你真的懂吗
- 虚函数 error LNK2001: 无法解析的外部符号 ";public: virtual void __cdecl
- OOP设计模式在路上(一)——简单工厂模式
- mysql配置utf8_mb4
- Houdini技术体系 基础管线(三) :UE4以选择区域的方式对地形做生成和更新 上篇
- 关于sublime Text 3安装sublimecodeIntel插件配置方法
- windows servier2008+virtualenv下部署Flask (IIS+wfastcgi)
- ajax post 数组
热门文章
- SPOJ QTREE4 - Query on a tree IV 树分治
- CodeForces 489F DP Special Matrices
- 带有命名空间的xml解析,C#
- 26、android上跑apache的ftp服务
- IDEA界面创建Scala的Maven项目
- python-高级编程-04
- oracle 可以连接数据库,vs连不上. 报错提示:ORA-12154: TNS: 无法解析指定的连接标识符
- TOJ 3581: 最简IPv6表示
- HDU——1418抱歉(平面欧拉公式)
- HDU-1534 Schedule Problem