题目重点：将 package 前置依赖建成有向图，用入度与小根堆输出确定性部署顺序，并检测环与未知依赖。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入为 package→prerequisite package 列表；每个依赖必须是输入中声明的包，重复依赖视为非法。
- 目标是输出任意合法部署顺序；为可复现，训练代码在多个可部署包中选字典序最小者。若有环报错，不执行真实部署。
解题路线
- 对 prerequisite→package 建边，统计每个 package 的入度；无依赖包可以先部署。
- 把入度为零的包入小根堆，弹出一个就输出，并将依赖它的包入度减一；新入度为零才可入堆。
- 若最终输出数量小于包数，剩余子图有环，无法满足所有依赖。未知依赖和重复边在建图阶段拒绝，避免入度与出边不匹配。
- 正确性不变量：堆中每个包的所有前置依赖都已输出；每次只输出堆内包，故部署序合法；若没有零入度节点且仍有剩余节点，就存在环。
手动走一遍
A 无依赖、B 依赖 A、C 依赖 A、D 依赖 B 与 C，输出可为 A,B,C,D。若 A 依赖 B 且 B 依赖 A，没有任何入度零包，报告环。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Deterministic deployment order from package -> prerequisites."""
from heapq import heappop, heappush
def deployment_order(requirements: dict[str, list[str]]) -> list[str]:
indegree = {package: 0 for package in requirements}
dependents = {package: [] for package in requirements}
for package, dependencies in requirements.items():
unique = set(dependencies)
if len(unique) != len(dependencies):
raise ValueError("duplicate dependency")
for dependency in unique:
if dependency not in requirements:
raise ValueError(f"unknown dependency: {dependency}")
indegree[package] += 1
dependents[dependency].append(package)
ready = []
for package, degree in indegree.items():
if degree == 0:
heappush(ready, package)
result = []
while ready:
package = heappop(ready)
result.append(package)
for dependent in dependents[package]:
indegree[dependent] -= 1
if indegree[dependent] == 0:
heappush(ready, dependent)
if len(result) != len(requirements):
raise ValueError("dependency cycle")
return result
复杂度
V 个包、E 条依赖，建图 O(V+E)，使用小根堆的确定性顺序总时间 O((V+E) log V)，空间 O(V+E)；若用普通队列，任意合法顺序可 O(V+E)。
易错点与追问
容易失分的边界
- 把边画成 package→dependency，却用错误入度顺序先部署依赖者。
- 只检测是否有循环，不输出合法顺序，未完成 LC210 方向。
- 重复依赖导致同一边计入度两次，却只在出边表减少一次。
继续深挖
- 若并行部署多个入度零的包，如何限制并发和失败传播？
- 某包部署失败后，已部署部分如何回滚或标记状态？
- Oracle Health 简化 course scheduler 帖称无多重依赖并要打印路径，但路径定义不明，不能直接当作本题同接口。
