解题思路
题意给出模块集合与依赖列表,每条依赖 [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) 加入答案。