LeetCode 补充题 23. 检测循环依赖
目录
题目描述
✅ 补充题 23. 检测循环依赖
题意分析
输入是节点总数
n和一组依赖dependencies，其中每条[a, b]表示「必须先完成a，才允许开始b」。要回答的是：这批依赖里有没有互相牵扯、导致谁都无法率先开工的情况。约束里有三个信号。其一，节点用
0到n - 1连续编号，可以直接拿数组下标当节点，不必再引入哈希表做映射。其二，依赖天然有方向，[a, b]和[b, a]含义完全相反，读入时把方向记反会得到完全不同的答案。其三，题目只要一个布尔判断，并不要求打印谁先谁后，但要判断得出来，内部仍然得真的把一个可行的开工顺序排出来——排得完就没问题，排不完就说明有节点被卡死了。边界要提前想清楚。
dependencies为空时任意顺序都合法，答案是不存在循环依赖。有些节点既不依赖别人、也没人依赖它，这类孤立节点同样在0到n - 1范围内，必须算进总数。[a, a]这种自依赖是最短的一种互相牵扯，要能被判出来。另外还要和面试官确认依赖是否可能重复给出，重复边会让同一个节点的「待满足前置数」被多加一次，但只要减的时候也走同一条边，计数依然自洽。
解法：拓扑排序统计可处理节点数
核心思路
问题关键：把任务看成有向图，
[a,b]表示边a→b。如果图中有环，环内每个节点都在等待另一个节点，无法形成覆盖全部节点的执行顺序；反之，有向无环图一定存在拓扑序。为什么选 Kahn 拓扑排序：入度为 0 的节点没有未完成前置，可以立即处理。处理它等价于删除它的所有出边；新的入度 0 节点继续入队。最终只需比较处理节点数和 n，无需枚举顺序，也避免 DFS 三色状态与递归栈。
不变量：
indegree[x]始终表示 x 尚未被删除的前置边数量；队列中只包含当前入度为 0 且尚未处理的节点。后继只在入度恰好降为 0 时入队，因此每个节点最多处理一次。正确性：若处理了 n 个节点，出队顺序就是合法拓扑序，所以无环。若队列耗尽时仍有节点未处理，剩余子图中每个节点入度都大于 0；从任一剩余节点沿前驱不断回溯，有限节点中必然重复到某个节点，形成环。因此
visited != n当且仅当存在循环依赖。
解题步骤
- 按
a→b建邻接表，并将indegree[b]加一。- 扫描全部
0...n-1，将所有入度为 0 的节点入队，孤立节点也不能漏掉。- 反复出队一个节点并计数；遍历它的后继，将后继入度减一，恰好减到 0 时入队。
- 队列为空后，若处理数小于 n 则有环，否则无环。
- 口述样例：
[[0,1],[0,2],[1,3],[2,3]]的初始入度为[0,1,1,2]，依次可处理0、1/2、3，处理数为 4，无环。若依赖为0→1→2→0，初始没有入度 0 节点，处理数为 0，存在环。
代码实现
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 个节点。
关键点总结
- “能否完成全部任务”就是“是否存在覆盖全部节点的拓扑序”。
- 入度表示当前尚未满足的前置数，只有减到 0 的瞬间才能入队。
- 要输出一个可行顺序，只需记录出队序列；要判断顺序是否唯一，可观察每轮队列是否只有一个节点。
- 结束后入度仍大于 0 的节点可能在环上，也可能只是被环阻塞，不能据此精确定位环节点。
易错点总结
- 漏掉孤立节点：
n=3, [[0,1]]中节点 2 也应入队并计入处理数，否则会把无环误判为有环。- 节点第一次被看到就入队：后继必须等所有前置都完成，即入度减到 0，不能只靠
visited去重。- 初始队列非空就返回无环：图中可能同时存在一个可处理入口和另一部分环，必须执行到队列耗尽再比较计数。
- 跳过自依赖：
[a,a]本身就是环，正常建图即可识别，不要特判删除。- 边去重不一致：若邻接表保留重复边，入度也必须按每条边计数；只在一侧去重会使入度无法正确归零。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 207. 课程表 | 中等 | 本题的原题形态，只回答能否修完 |
| 210. 课程表 II | 中等 | 判环之外还要把出队序列作为答案返回 |
| 269. 火星词典 | 困难 | 难点在从相邻单词的首个差异字符里推出边 |
| 310. 最小高度树 | 中等 | 无向图变形，从度为 1 的叶子逐层剥到中心 |
| 444. 序列重建 | 中等 | 判定拓扑序是否唯一，看每轮队列长度是否为 1 |
| 630. 课程表 III | 困难 | 与图无关，是按截止时间排序加堆的反悔贪心 |
| 1462. 课程表 IV | 中等 | 求依赖的传递闭包，需要可达性而非顺序 |
| LCR 113. 课程表 II | 中等 | 210 的同题改编，返回任意一个可行顺序 |
| LCR 114. 火星词典 | 困难 | 269 的同题改编，注意非法前缀要先判空 |
| LCR 115. 序列重建 | 中等 | 444 的同题改编，验证唯一重建 |
| 面试题 04.01. 节点间通路 | 中等 | 只问两点是否可达，一次搜索即可，无需入度 |