AlgoMooc
← 返回题库

P3750. 启动多任务排序

中等通过率 48% · 提交 958 · 通过 460
BFS拓扑排序图论排序

小慕正在开发一个应用启动器,应用启动时需要执行多个初始化任务,这些任务之间存在。例如,任务A依赖任务B,意味着必须等任务B执行完成后,才能开始执行任务A。 现在小慕拿到了多条任务依赖规则,需要输出任务的执行顺序。规则采用:如果一个任务没有依赖任何其他任务,就立刻开始执行;如果同时有多个任务可以执行,则按照任务名称的字母顺序排序。 例如:任务B依赖任务A,任务C依赖任务A,任务D依赖任务B和任务C,同时任务D还依赖任务E。那么任务的执行顺序由先到后是:任务A,任务E,任务B,任务C,任务D。这里任务A和任务E都没有依赖,所以立即执行。

提示:带虚线的词点一下有通俗解释。

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系,输入参数中符号->表示依赖方向,例A->B表示A依赖B,多个依赖之间用单个空格分割

输出描述

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

示例

示例 1

输入

B->A C->A D->B D->C D->E

输出

A E B C D

示例 2

输入

A->B C->B

输出

B A C

说明:任务A和C都依赖于任务B。任务B执行后,A和C立即执行,A和C的执行顺序按照字典序排列。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。