本题实质上是求 所有合法的拓扑排序。
给定依赖关系 [依赖模块, 被依赖模块],意味着:
[A, B] 表示 B -> A(B 必须先构建,A 才能构建)。某公司正在开发一个大型软件系统,系统包含 N 个模块,每个模块之间存在构建依赖关系。例如,模块 A 可能依赖于模块 B,这意味着必须先构建模块 B,才能构建模块 A。
请根据依赖关系,输出所有可能的模块构建顺序(按照构建顺序排列模块名称),要求:
每个合法的构建顺序作为一个结果
多个结果按字典序排序后输出
如果存在循环依赖(依赖成环的情况),则说明没有合法的构建顺序,返回空数组
["模块名 1","模块名 2", ..., "模块名 N"]
[[依赖模块,被依赖模块], [依赖模块,被依赖模块], ...]
第一个参数:所有模块名称组成的一维数组,模块名只会由数字、大写字母、小写字母构成,无分隔符。模块名称互不相同。(模块数量 N≤100)
第二个参数:依赖关系组成的二维数组,每个元素是 [依赖模块, 被依赖模块] 表示前者依赖后者。被依赖模块必须在依赖模块之前构建。(依赖关系数量 <100)
输出所有合法的构建顺序,模块之间用空格分隔,按字典序排序。(保证合法构建顺序结果 <10!)
备注:10!=10×9×8×7×6×5×4×3×2×1
输入
["user","auth","database","api"],[["user","auth"],["auth","database"],["api","database"]]
输出
["database api auth user","database auth api user","database auth user api"]
说明
输入
["A","B","C"],[["A","B"],["B","C"],["C","A"]]
输出
[]
说明
形成环 A→B→C→A,存在循环依赖,无法完成构建,输出为空。