解题思路
题意给出模块集合与依赖列表,每条依赖 [x, y] 表示 x 依赖 y,即合法构建顺序中 y 必须出现在 x 的左侧。在图论上,将每条依赖建成有向边 y→x(先构建 y,再构建 x),问题转化为求 所有拓扑排序。
- 判环:若图存在有向环,则不存在能包含全部顶点的拓扑序,应返回空数组。可用 Kahn 算法(不断删除入度为 0 的顶点并删边)统计能否删完 N 个顶点;若不能,说明有环。
- 枚举所有拓扑序:在确认无环后,用 DFS + 回溯 维护当前路径
path 与动态入度表 indeg:
- 每一步在「尚未放入路径且当前入度为 0」的模块中,按 模块名字典序 依次尝试(保证搜索顺序稳定,但最终仍需对生成的整行字符串列表排序,与题意「多条结果按字典序」一致)。
- 选中模块 m 后,将其加入路径,并对所有 m→v 的边执行
indeg[v]--;回溯时恢复。
- 当路径长度达到 N 时,将
" ".join(path) 加入答案。
P14195.项目模块依赖构建顺序规划(200分)
题目内容
某公司正在开发一个大型软件系统,系统包含 N 个模块,每个模块之间存在构建依赖关系。例如,模块 A 可能依赖于模块 B,这意味着必须先构建模块 B,才能构建模块 A。
请根据依赖关系,输出所有可能的模块构建顺序(按照构建顺序排列模块名称),要求:
-
每个合法的构建顺序作为一个结果
-
多个结果按字典序排序后输出
-
如果存在循环依赖(依赖成环的情况),则说明没有合法的构建顺序,返回空数组
输入描述
["模块名 1","模块名 2", ..., "模块名 N"]
[[依赖模块,被依赖模块], [依赖模块,被依赖模块], ...]
-
第一个参数:所有模块名称组成的一维数组,模块名只会由数字、大写字母、小写字母构成,无分隔符。模块名称互不相同。(模块数量 N≤100)
-
第二个参数:依赖关系组成的二维数组,每个元素是 [依赖模块, 被依赖模块] 表示前者依赖后者。被依赖模块必须在依赖模块之前构建。(依赖关系数量 <100)
输出描述
输出所有合法的构建顺序,模块之间用空格分隔,按字典序排序。(保证合法构建顺序结果 <10!)
备注:10!=10×9×8×7×6×5×4×3×2×1
样例1
输入
["user","auth","database","api"],[["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
输入
["A","B","C"],[["A","B"],["B","C"],["C","A"]]
输出
[]
说明
形成环 A→B→C→A,存在循环依赖,无法完成构建,输出为空。