小慕正在负责一个大型软件项目,项目包含 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