24. Detect Cycle in Module Dependency Graph
Origin: Detect Cycle in Module Dependency Graph
Given n modules labeled 0 to n-1 and a list of directed edges dependencies where [u, v] means module u depends on module v, detect whether there is a circular dependency (cycle) in the graph.
Example 1
Input: n = 4, dependencies = [[1, 0], [2, 1], [3, 2]]
Output: 0
Explanation: 边为 1→0, 2→1, 3→2。形成简单链，没有模块间接或直接依赖回自己，无环。
Example 2
Input: n = 4, dependencies = [[1, 0], [2, 1], [0, 2]]
Output: 1
Explanation: 边为 1→0, 2→1, 0→2。0 依赖 2，2 依赖 1，1 依赖 0，形成环 0→2→1→0。
Input Format
- 第一行：n（模块数量）
- 第二行：dependencies 数组长度
- 接下来每行：dependencies 数组的元素
Constraints
- 1 <= n <= 1000
- 0 <= dependencies.length <= n * (n - 1)
- dependencies[i].length == 2
- 0 <= dependencies[i][0] < n
- 0 <= dependencies[i][1] < n
Output Format
返回整数：1 表示有环，0 表示无环。
Sample Input 0
1
0
0
Sample Output 0
0
Sample Input 1
1
1
2
0
0
Sample Output 1
1
函数契约
// 输入：n（节点数），dependencies（有向边列表，[u, v] 表示 u 依赖 v）
// 输出：1（有环）或 0（无环）
// 边界：无依赖 → 0；自环 → 1；两节点互指 → 1
边界表
| 场景 | 返回什么 |
|---|---|
| 无边 | 0 |
| 单节点无边 | 0 |
| 链式无环 | 0 |
| 三角形环 | 1 |
| 两节点互指 | 1 |
| 部分有环 | 1 |
Resolution
我的解法
function hasCircularDependency(n: number, dependencies: number[][]): boolean {
const graph: Record<number, number[]> = {};
const colors: Record<number, number> = {}; // 0: 未访问, 1: 访问中, 2: 已完成
for (let i = 0; i < n; i++) {
graph[i] = [];
colors[i] = 0;
}
for (const [from, to] of dependencies) {
graph[from].push(to);
}
let res = false
const dfs = (index: number) => {
if (res) return
colors[index] = 1; // 标记为访问中
for (const neighbor of graph[index]) {
if (colors[neighbor] === 1) {
res = true // 遇到灰色节点 = 环
return
}
if (colors[neighbor] === 2) {
continue // 已完成，跳过
}
dfs(neighbor);
}
colors[index] = 2; // 标记为已完成
}
for (let i = 0; i < n; i++) {
if (colors[i] === 0) {
dfs(i)
}
}
return res
}解题思路
三色标记法（DFS 环检测）：
- 白色（0）：未访问
- 灰色（1）：正在访问中（在当前 DFS 路径上）
- 黑色（2）：已访问完（整棵子树遍历完）
核心逻辑：DFS 过程中如果遇到灰色节点，说明当前路径上又回到了自己，存在环。
A → B → C → A
访问 A：A 标灰
访问 B：B 标灰
访问 C：C 标灰
访问 C 的邻居 A：A 是灰色 → 发现环！
为什么灰色表示环？灰色意味着”这个节点在当前递归路径上还没走完”。如果 DFS 到一半又回到这个节点，说明有一条边从后代指回了祖先。
注意：有向图建邻接表时每条边只加一次（adj[from].push(to)），不是无向图那样加两次。
踩坑经历
- 建图时用
dependencies[i]而非遍历 dependencies：dependencies 的长度可能不等于 n，应该先初始化 n 个节点，再遍历 dependencies 填边。 - 黑色标记漏了：DFS 结束时没把节点标黑，回溯后节点还是灰色，其他路径经过它会误判为环。
- 黑色节点应该 continue 不是 return：
return会跳过当前节点后续的其他邻居，应该用continue只跳过这个邻居。
复杂度
- 时间：O(n + m)，n 是节点数，m 是边数，每个节点和每条边访问一次
- 空间：O(n + m)，邻接表 O(n + m)，colors 数组 O(n)，递归栈最深 O(n)
参考来源
- 相关题型：图论
- 相关文章：算法解题流程：从读题到提交的七步
- 相关题目：21. Count Connected Components in Network — 同样是图论 DFS，第 21 题是连通分量，第 24 题是环检测