题目分析
- 问题本质：判断有向图是否存在环。课程之间的先修关系构成一个有向图，若图不存在有向环，则可完成所有课程；若存在环，则不可完成。
- 输入输出：
- 输入：
- 第一行：numCourses（课程总数）
- 第二行：m（先修关系条数）
- 接下来 m 行：a b，表示课程 a 需要先修课程 b，即有边 b -> a
- 输出：一行 "true" 或 "false"
- 约束：
- 1 <= numCourses <= 1e5
- 0 <= m <= 2e5
- 0 <= a, b < numCourses
- 需要时间复杂度 O(numCourses + m)
解题思路
常见两种方法：
-
拓扑排序（Kahn 算法，BFS）
- 思想：统计每个节点的入度，将入度为 0 的课程入队，逐步“上课”并移除其对后继课程的影响（后继入度减 1）。最终若能处理完所有课程（出队计数等于 numCourses），则无环；否则有环。
- 优点：迭代实现，无递归栈风险；时间 O(n + m)，空间 O(n + m)。
- 适合本题大规模数据。
-
DFS 检测环
- 思想：对每个未访问节点进行 DFS，使用三色标记（0=未访问, 1=访问中, 2=已完成）。在访问中再次遇到访问中的节点，说明存在回边（有向环）。
- 优点：实现简洁，直观。
- 缺点：Java 在最坏情况下（长链）可能栈溢出；需注意递归深度限制。
对比与选择：
- 在本题规模下（最多 1e5 节点、2e5 边），推荐使用 Kahn 拓扑排序（BFS），更稳健，不会栈溢出。DFS 方法可作为参考实现。
算法设计（选定：Kahn 拓扑排序）
- 数据结构：
- 邻接表 graph：ArrayList[]，graph[u] 存储从 u 指向的后继 v（b -> a）
- 入度数组 indeg：indeg[v] 表示 v 的入度
- 队列 queue：存入所有入度为 0 的节点
- 步骤：
- 初始化邻接表和入度数组。
- 遍历所有先修关系 (b -> a)，填充 graph[b].add(a)，并 indeg[a]++。
- 将所有入度为 0 的课程入队。
- 出队一个课程 u，计数 processed++；遍历 u 的后继 v，执行 indeg[v]--；若 indeg[v] == 0，则入队 v。
- 循环结束后，若 processed == numCourses，则返回 true；否则返回 false。
- 边界情况处理：
- m == 0：所有课程入度均为 0，直接返回 true。
- 自环（a == b）：会导致 indeg[a] >= 1，最终 processed < numCourses，返回 false。
- 重边（重复的先修关系）：入度会相应累加，拓扑排序正确处理。
代码实现（Java）
说明：
- 提供两种方法：Kahn（主方法）与 DFS（参考）。
- 包含 main 方法，按题目输入格式读取并输出结果。
- 同时提供 LeetCode 风格的 canFinish 方法。
import java.io.*;
import java.util.*;
/**
* 课程表（是否可修完）
* 方法一：Kahn 拓扑排序（BFS） —— 推荐
* 方法二：DFS 检测有向环 —— 参考（可能有递归栈风险）
*/
public class Solution {
// LeetCode风格函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
return canFinishKahn(numCourses, prerequisites);
}
// 方法一：Kahn 拓扑排序
public boolean canFinishKahn(int n, int[][] prerequisites) {
// 邻接表
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
// 入度
int[] indeg = new int[n];
// 构图：b -> a
for (int[] e : prerequisites) {
int a = e[0], b = e[1];
graph[b].add(a);
indeg[a]++;
}
// 入度为0的节点入队
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) queue.offer(i);
}
int processed = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
processed++;
for (int v : graph[u]) {
if (--indeg[v] == 0) {
queue.offer(v);
}
}
}
return processed == n;
}
// 方法二：DFS 检测环（参考实现）
public boolean canFinishDFS(int n, int[][] prerequisites) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : prerequisites) {
int a = e[0], b = e[1];
graph[b].add(a);
}
// 0=未访问, 1=访问中, 2=已完成
int[] state = new int[n];
for (int i = 0; i < n; i++) {
if (state[i] == 0) {
if (dfsHasCycle(i, graph, state)) {
return false; // 有环则不可完成
}
}
}
return true;
}
private boolean dfsHasCycle(int u, List<Integer>[] graph, int[] state) {
state[u] = 1; // 标记为访问中
for (int v : graph[u]) {
if (state[v] == 1) return true; // 回边：有环
if (state[v] == 0 && dfsHasCycle(v, graph, state)) return true;
}
state[u] = 2; // 完成
return false;
}
// 主程序：按题目输入格式读取并输出
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s;
s = br.readLine();
if (s == null) return;
int numCourses = Integer.parseInt(s.trim());
s = br.readLine();
int m = Integer.parseInt(s.trim());
int[][] prerequisites = new int[m][2];
for (int i = 0; i < m; i++) {
String line = br.readLine();
StringTokenizer st = new StringTokenizer(line);
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
prerequisites[i][0] = a;
prerequisites[i][1] = b;
}
Solution sol = new Solution();
boolean ans = sol.canFinishKahn(numCourses, prerequisites);
System.out.println(ans ? "true" : "false");
}
}
复杂度分析
- 时间复杂度：
- 构图 O(n + m)
- Kahn 拓扑排序遍历每条边一次 O(m)，每个节点入队、出队一次 O(n)
- 总计 O(n + m)
- 空间复杂度：
- 邻接表存储 O(n + m)
- 入度数组 O(n)
- 队列最多 O(n)
- 总计 O(n + m)
测试用例
- 示例1：
- 示例2：
- 输入：
- numCourses=2, m=2
- 1 0
- 0 1
- 输出：false
- 边界用例：
- 无先修关系：
- 输入：numCourses=5, m=0
- 输出：true
- 自环：
- 输入：numCourses=1, m=1
- 0 0
- 输出：false
- 长链（压力测试，栈安全性验证对 DFS 不利）：
- 输入：numCourses=5, m=4
- 1 0
- 2 1
- 3 2
- 4 3
- 输出：true
说明：在大规模数据下建议采用 Kahn 拓扑排序方案，避免递归带来的栈溢出风险。
