LeetCode 补充题 23. 检测循环依赖
题目描述
:::fold-green 相关原题
✅ 207. 课程表
LeetCode 原题中 [a,b] 表示 b → a，能完成全部课程时返回 true；本文中 [a,b] 表示 a → b，存在环时返回 true。
:::
给定
n个任务以及有向依赖数组dependencies，请判断这些依赖关系中是否存在环。任务编号为
0到n - 1，每条[a,b]表示有向边a → b：任务b必须等待任务a完成后才能执行。存在循环依赖时返回
true，否则返回false。任务之间可以互不相连，没有出现在依赖数组中的任务也属于这n个任务。
示例 1：
输入：n = 3, dependencies = [[0,1],[1,2],[2,0]]
输出：true
解释：三个任务形成 0 → 1 → 2 → 0 的循环。
示例 2：
输入：n = 3, dependencies = [[0,1],[1,2]]
输出：false
提示：
-
n >= 0，所有边的端点都属于合法任务编号。 - 自己依赖自己的任务也会形成环。
- 本题返回“是否有环”，与返回“是否能完成所有任务”的接口含义相反。
题意分析
判断一组有向依赖关系中是否存在循环：沿依赖边出发，经过若干条边又回到原节点，就形成了环。有环时，相关任务之间会相互等待，无法按依赖顺序全部完成。
下文沿用现有
hasCycle(n, dependencies)接口：节点编号为0..n - 1，每条[a, b]按a → b建图，表示处理b之前需要先处理a。返回true表示有环，不是表示所有任务都能完成；未出现在任何边中的节点也属于需要统计的节点。
解法：拓扑排序统计可处理节点数
核心思路
[!blue]
入度表示一个节点还有多少条尚未解除的前置依赖。入度为
0的节点当前没有等待对象，可以先处理；处理它后，相当于删除它发出的所有边，让每个后继的入度减少相应次数。新出现的零入度节点也就可以继续处理。这就是拓扑排序的 Kahn 算法。用队列保存已经可以处理的节点，用
visited记录实际处理数量。删除过程始终维护“剩余图中的入度”，所以一个节点只有在全部前置都被删除后才会进入队列。如果原图有环，环上每个节点至少还依赖前一个环内节点，在任何一个环节点先被处理之前，这条依赖都无法解除。因此环不可能被上述过程全部删除。
反过来，如果队列已经为空却还有节点，剩余每个节点的入度都大于
0。从任意剩余节点不断沿入边寻找前驱，因为节点数有限，最终必然重复经过某个节点，构成环。因此处理数等于n时无环，小于n时有环，两种情况覆盖全部可能。图可能包含互不相连的部分，所以初始化时必须扫描全部节点，把所有零入度节点都入队。存在一个可处理的部分，并不能说明其他部分也没有环。
解题步骤
- 为每个节点建立邻接表，记录它指向哪些后继；每加入一条
a → b，同步令indegree[b]++。- 扫描所有节点，将入度为
0的节点入队，包括孤立节点。- 每次出队一个节点，将处理数加一，再遍历它的所有出边，把对应后继的入度减一。
- 后继入度恰好降为
0时，将它加入队列。- 队列耗尽后返回
visited != n，表示是否仍有无法消除的依赖环。
代码实现
class Solution {
public boolean hasCycle(int n, int[][] dependencies) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
int[] indegree = new int[n];
for (int[] edge : dependencies) {
graph[edge[0]].add(edge[1]);
indegree[edge[1]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int visited = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
visited++;
// 删除当前节点的出边，释放后继节点依赖。
for (int next : graph[node]) {
indegree[next]--;
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
return visited != n;
}
}
func hasCycle(n int, dependencies [][]int) bool {
graph := make([][]int, n)
indegree := make([]int, n)
for _, edge := range dependencies {
from := edge[0]
to := edge[1]
graph[from] = append(graph[from], to)
indegree[to]++
}
queue := make([]int, 0)
for node := 0; node < n; node++ {
if indegree[node] == 0 {
queue = append(queue, node)
}
}
visited := 0
for head := 0; head < len(queue); head++ {
node := queue[head]
visited++
// 后继节点入度降为 0 后才可以进入拓扑序。
for _, next := range graph[node] {
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
return visited != n
}
复杂度分析
- 时间复杂度：$O(V+E)$。每个节点最多入队、出队一次，每条边只在建图和删除时各访问一次。
- 空间复杂度：$O(V+E)$。邻接表保存所有边，入度数组和队列至多保存 V 个节点。
关键点总结
[!green]
- 删除零入度节点不会遗漏任何环；处理结束后仍有节点，则剩余图一定含环。
- 邻接表与入度必须按同一个边方向维护，删除的边要与初始计数一一对应。
- 剩余节点可能在环上，也可能只是依赖环而被阻塞，处理数只能判环，不能直接给出全部环节点。
易错点总结
[!yellow]
- 只从边中收集初始节点，会漏掉孤立节点，导致处理数不足而误判有环。
- 后继第一次被访问就入队，忽略了它可能还有其他前置依赖；必须等入度降到
0。- 初始队列非空就判断无环，可能遗漏其他连通部分中的循环。
- 自依赖本身就是环，不能在建图时删除。
- 邻接表保留重复边、入度却只计一次，或反过来只在一侧去重，都会破坏计数；两处应采用一致规则。
- 本接口问的是“是否有环”，不要把返回值写成表示可完成全部任务的
visited == n。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 207. 课程表 | 中等 | 同样用拓扑处理节点数判断环；本题报告有环时，课程表对应不能完成，返回语义相反。 |
| 210. 课程表 II | 中等 | 判定无环后可进一步输出拓扑顺序，但输入边方向仍需按各题定义建立。 |