Uber 服务依赖判环：合并多份依赖数组

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入服务 ID 集合，以及一份或多份 (service,dependency) 关系；服务必须在所列依赖服务完成后启动。
• 判定这些依赖合起来是否包含有向环；重复边只算一次。若边引用未知服务，示例代码报错，而非默默新增。
• 空服务集或完全无依赖的图无环；自依赖 (A,A) 是环。

解题路线

1. 先把所有数组的边合并成集合；按 dependency→service 建邻接表，service 的入度为其不同前置依赖数。
2. 将入度为 0 的服务全部入队。反复弹出可启动服务，删除其对后续服务的约束，产生新入度 0 的服务继续入队。
3. 若最后被处理的服务数小于总数，则余下服务在至少一个有向环中或依赖于环，判为有环；否则给出的弹出顺序也是一条合法启动顺序。

手动走一遍

数组一含 A 依赖 B、数组二含 B 依赖 C，合并后 C→B→A，无环。再加 C 依赖 A，就有 A→C→B→A，队列无法处理全部节点。重复写一次 A 依赖 B 不能把入度加两次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Detect a cycle after merging multiple service dependency lists."""

from collections import deque


def has_service_cycle(services: set[str], dependency_lists: list[list[tuple[str, str]]]) -> bool:
    graph = {service: set() for service in services}
    indegree = {service: 0 for service in services}
    for edges in dependency_lists:
        for service, dependency in edges:
            if service not in graph or dependency not in graph:
                raise ValueError("dependency references unknown service")
            if service not in graph[dependency]:
                graph[dependency].add(service)
                indegree[service] += 1
    ready = deque(service for service, degree in indegree.items() if degree == 0)
    processed = 0
    while ready:
        dependency = ready.popleft()
        processed += 1
        for service in graph[dependency]:
            indegree[service] -= 1
            if indegree[service] == 0:
                ready.append(service)
    return processed != len(services)

复杂度

设服务数 V、去重后关系数 E；合并与 Kahn 遍历期望 O(V+E) 时间、O(V+E) 空间（哈希集合去重）。若需要返回具体环，可另做三色 DFS，仍为 O(V+E)。

易错点与追问

容易失分的边界

• 分别判每个 dependency array 无环，不代表合并后无环；环可跨数组形成。
• 重复边若只去重邻接表却仍多加一次入度，会误判成环。
• 方向可任选一致约定来判环，但若还要输出启动顺序，必须明确 dependency→service 的方向。

继续深挖

• 工程环境需记录环的具体服务链、来源数组和配置版本，让部署者能定位错误；Kahn 只给布尔结果时可对剩余子图再做 DFS 找 witness。
• 若依赖配置动态增加，新增边可立即验证是否从 dependency 可回到 service；动态删边和高频查询则需更复杂索引或定期重建拓扑。