L2-026

### 关于L2-026的相关IT内容 #### 问题描述 L2-026 是 PAT 天梯赛中的一道题目，主要涉及广度优先搜索（BFS）算法的应用。该题的核心在于通过构建家族树结构并遍历找到最小辈分的成员列表[^2]。 #### 输入与输出说明 输入部分提供了家族总人数 \(N\) 和每位成员的父亲/母亲编号。对于根节点的老祖宗，其父亲/母亲编号设定为 \(-1\) 表明无上级节点存在[^3]。最终目标是计算出最小辈分以及这些成员的具体编号，并按照升序排列输出结果[^4]。 #### 解决方案概述 解决此问题的关键步骤如下： - 构建图或者树形数据结构表示家庭关系； - 使用 BFS 遍历整个树状结构以定位最深层即最低代次的所有个体； - 对获取的结果集进行排序处理以便满足输出需求； 以下是基于 Python 实现的一个可能解决方案： ```python from collections import deque, defaultdict def find_min_generation(n, parents): graph = defaultdict(list) root = None # 建立子到父的关系映射 同时寻找root children_map = defaultdict(list) for child in range(1, n+1): parent = parents[child-1] if parent != -1: children_map[parent].append(child) else: root = child queue = deque() visited_generations = {} # 初始化队列 加入起点 并记录初始代数 queue.append((root, 1)) while(queue): current_node, generation = queue.popleft() if(current_node not in visited_generations or (current_node in visited_generations and visited_generations[current_node]>generation)): visited_generations[current_node]=generation # 添加所有孩子进入queue 更新他们的gen number for kid in children_map.get(current_node, []): queue.append((kid, generation + 1)) min_gen = min(visited_generations.values()) result_members = sorted([node for node, gen in visited_generations.items() if gen==min_gen]) return min_gen, result_members if __name__ == "__main__": num_people = int(input().strip()) # 获取人口数量 parental_relations = list(map(int, input().split()))[:num_people] minimum_generation, members_of_minimum_gen = find_min_generation(num_people, parental_relations) print(minimum_generation) print(' '.join(str(member) for member in members_of_minimum_gen)) ``` 上述代码实现了从读取输入至完成输出的整体流程，利用了 `collections` 库中的 `deque` 来辅助实现高效的 BFS 过程^。 ###