华为OD机考双机位C卷 - 启动多任务排序 （Java Python JS GO C++ C）

# 启动多任务排

2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷

华为OD机试双机位C卷真题目录点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（OD上机考试双机位C卷）

题目描述

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。

现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。

例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：

A任务，E任务，B任务，C任务，D任务

这里A和E任务都是没有依赖的，立即执行。

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号"->"表示依赖方向，例如：

A->B：表示A依赖B

多个依赖之间用单个空格分隔

输出描述

输出排序后的启动任务列表，多个任务之间用单个空格分隔

用例

输入

A->B C->B

输出

B A C

解题思路

1. 构建图的邻接表和计算每个任务的入度。邻接表graph用于表示任务间的依赖关系，而入度表inDegree用于记录每个任务依赖的任务数量。
2. 遍历输入的依赖关系，更新邻接表和入度表。对于每个依赖A->B，将B添加到A的邻接列表中，并将B的入度加1。同时，确保每个任务至少在入度表中出现一次，如果任务没有依赖，则其入度为0。
3. 使用一个队列（或列表）来收集入度为0的任务，即可以立即执行的任务。
4. 按照字母顺序执行入度为0的任务，并在执行过程中更新其它任务的入度。对于每个执行的任务，检查它的所有后继任务，将每个后继任务的入度减1。如果后继任务的入度减为0，则将其加入到下一轮执行的队列中。
5. 重复步骤4，直到没有任务可以执行。

用例A->B C->B模拟计算过程：

• 输入：A->B C->B
• 分割输入，得到依赖关系：A依赖于B，C依赖于B。
• 构建邻接表和入度表：
  • 邻接表：B -> [A, C]（B完成后，可以执行A和C）
  • 入度表：A: 1, C: 1, B: 0（A和C各有1个依赖，B没有依赖）
• 由于B的入度为0，它可以立即执行。执行B，更新队列。
• 执行B后，更新A和C的入度，它们的入度都变为0，可以执行。将A和C加入执行队列。
• 根据字母顺序，先执行A，然后执行C。
• 最终输出的执行顺序为：B A C。