AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

N0017. 0426-项目模块依赖构建顺序规划

中等通过率 55% · 提交 42 · 通过 23
回溯拓扑排序图论

小慕正在负责一个大型软件项目,项目包含 N 个模块,模块之间存在构建。例如,模块 A 可能依赖于模块 B,这意味着必须先构建模块 B,才能构建模块 A。 请根据依赖关系,输出所有可能的模块构建顺序(按照构建顺序排列模块名称),要求: 1. 每个合法的构建顺序作为一个结果 2. 多个结果按排序后输出 3. 如果存在(依赖成环的情况),则说明没有合法的构建顺序,返回空数组

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

输入描述

第一个参数为一个一维字符串数组表示所有模块名称,模块名只会由数字、大写字母、小写字母构成,无分隔符。模块名称互不相同。(模块数量 N≤100) 第二个参数为一个二维字符串数组,内层二维数组表示依赖关系。每个依赖关系为依赖模块,被依赖模块,表示前者依赖后者。被依赖模块必须在依赖模块之前构建。多个依赖关系使用空格分割。依赖关系数量 <100

输出描述

输出所有合法的构建顺序,模块之间用空格分隔,按字典序排序。(保证合法构建顺序结果 <10!)存在循环依赖返回空数组。

示例

示例 1

输入

4
user auth database api
3
user auth
auth database
api database

输出

database api auth user
database auth api user
database auth user api

说明:依赖关系:user→auth→database,api→database database所有模块都依赖,需要第一个构建 合法拓扑排序有 3 种,按字典序排序后输出

示例 2

输入

3
A B C
3
A B
B C
C A

输出

NULL

说明:形成环 A→B→C→A,存在循环依赖,无法完成构建,返回空数组。

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

看不懂题目?点开图解
模块依赖关系图(示例) database auth user api 依赖 依赖 依赖 模块 依赖方向(箭头指向被依赖模块)
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「0426-项目模块依赖构建顺序规划」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。