1004 Counting Leaves (Python实现)

今天药忘吃喽~ 2023-06-19 06:52 13阅读 0赞

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

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

### Python实现： ###

def dfs(node, depth):
        is_visited[node] = True
        global max_depth
        max_depth = max(max_depth, depth)
        if node not in tree:
            num_leaf_node[depth] += 1
            return
        for child in tree[node]:
            if child not in is_visited:
                dfs(child, depth + 1)  # 递归
    
    
    n, m = list(map(int, input().split()))  # n:树中节点数,m:非叶节点数
    tree = {}  # 用字典表示树
    max_depth = 0  # 树的深度
    num_leaf_node = [0] * (n + 1)  # 同一深度的叶子节点数
    is_visited = {}  # 节点是否已访问
    for i in range(m):  # 初始化树
        node_id, children, *child_id = input().split()  # 如果化成int处理，测试点4报非零返回
        tree[node_id] = child_id
    dfs('01', 0)
    print(" ".join(str(i) for i in num_leaf_node[0:max_depth + 1]))

### 提交结果： ###

<table> 
 <thead> 
  <tr> 
   <th>提交时间</th> 
   <th>状态</th> 
   <th>分数</th> 
   <th>题目</th> 
   <th>编译器</th> 
   <th>耗时</th> 
   <th>用户</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>2019/12/4 22:11:44</td> 
   <td> <p>答案正确</p> </td> 
   <td>30</td> 
   <td><a href="https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184" rel="nofollow">1004</a></td> 
   <td>Python (python 3)</td> 
   <td>22 ms</td> 
   <td>哆啦一泓</td> 
  </tr> 
 </tbody> 
</table>