2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某公司正在开发一个大型软件系统，系统包含 $N$ 个模块，每个模块之间存在构建依赖关系。例如，模块 $A$ 可能依赖于模块 $B$，这意味着必须先构建模块 $B$，才能构建模块 $A$。

请根据依赖关系，输出所有可能的模块构建顺序（按照构建顺序排列模块名称），要求：

1. 每个合法的构建顺序作为一个结果

2. 多个结果按字典序排序后输出

3. 如果存在循环依赖（依赖成环的情况），则说明没有合法的构建顺序，返回空数组

输入描述

["模块名 $1$","模块名 $2$", ..., "模块名 $N$"]

[[依赖模块，被依赖模块], [依赖模块，被依赖模块], ...]

• 第一个参数：所有模块名称组成的一维数组，模块名只会由数字、大写字母、小写字母构成，无分隔符。模块名称互不相同。（模块数量 $N \le 100$）

• 第二个参数：依赖关系组成的二维数组，每个元素是 [依赖模块, 被依赖模块] 表示前者依赖后者。被依赖模块必须在依赖模块之前构建。（依赖关系数量 $< 100$）

输出描述

输出所有合法的构建顺序，模块之间用空格分隔，按字典序排序。（保证合法构建顺序结果 $< 10!$）

备注：$10! = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 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$，存在循环依赖，无法完成构建，输出为空。

解题思路

核心思想

本题本质上是一个求解有向图中所有合法拓扑排序（Topological Sort）的问题。 给定一组模块和依赖关系，模块的构建顺序必须满足依赖条件，即“被依赖的模块”必须在“依赖模块”之前构建。在有向图中，这意味着从“被依赖模块”指向“依赖模块”的一条有向边。

由于题目要求：

1. 输出所有合法的构建顺序。
2. 若存在循环依赖（即图中存在环），则返回空。
3. 多个结果按字典序排序输出。

我们可以通过 回溯算法（DFS） + 拓扑排序 来实现。 为了确保最终生成的序列字符串按字典序排列，我们可以在处理前，将所有模块名称预先按字母顺序进行升序排序。这样在回溯过程中，我们按照固定的顺序遍历入度为 的节点，天然地就能保证生成的拓扑排序序列符合字典序要求，避免了在最后阶段收集全部结果再进行大规模排序，从而极大地优化了性能。如果在遍历完成后发现生成的序列长度不等于总模块数，说明存在环，直接输出空即可。

复杂度分析

• 时间复杂度：$O(V + E + K \cdot V)$，其中 $V$ 是模块数量，$E$ 是依赖关系数量，$K$ 是合法的拓扑排序个数。最坏情况下（无任何依赖）排序个数为 $V!$，但题目保证合法构建顺序结果 $< 10!$。
• 空间复杂度：$O(V + E)$，主要用于存储邻接表、入度数组以及回溯时的路径数组和递归调用栈。