vvrf / DSA.log

问题拆解

numCourses 门课，prerequisites 里的 [a, b] 表示修 a 之前必须先修 b，问能否修完所有课。把每门课看成节点、每条先修关系看成 b -> a 的有向边，问题就变成：这张有向图有没有环？无环就存在一个合法的修课顺序（拓扑序），有环则环上的课互相等待，谁也修不了。

怎么判环？模拟现实里的选课过程：一门课能开修，当且仅当它的所有先修课都已修完——对应图上“入度为 0”。修完它之后，依赖它的课程各自少了一门先修课——对应“把它的出边删掉，邻居入度减一”。不断重复“找入度 0 的点、摘掉、更新邻居”，这就是 Kahn 拓扑排序。

环上的每个节点都有一条来自环内的入边，无论外围怎么摘，它们的入度永远到不了 0，于是永远进不了队列。“摘掉的点数 < 总数”与“有环”是一回事。

入度表加队列的拓扑排序

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]); // 先修 p[1] 才能修 p[0]
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i); // 没有先修课，直接可修
        }
    }
    int finished = 0;
    while (!queue.isEmpty()) {
        int cur = queue.poll();
        finished++;
        for (int next : graph.get(cur)) {
            if (--indegree[next] == 0) { // 先修课清零，解锁
                queue.offer(next);
            }
        }
    }
    return finished == numCourses;
}

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)  # 先修 b 才能修 a
        indegree[a] += 1

    queue = deque(i for i in range(numCourses) if indegree[i] == 0)  # 没有先修课，直接可修
    finished = 0
    while queue:
        cur = queue.popleft()
        finished += 1
        for nxt in graph[cur]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:  # 先修课清零，解锁
                queue.append(nxt)
    return finished == numCourses

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)
    for _, p := range prerequisites {
        graph[p[1]] = append(graph[p[1]], p[0]) // 先修 p[1] 才能修 p[0]
        indegree[p[0]]++
    }
    queue := []int{}
    for i, d := range indegree {
        if d == 0 {
            queue = append(queue, i) // 没有先修课，直接可修
        }
    }
    finished := 0
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        finished++
        for _, next := range graph[cur] {
            indegree[next]--
            if indegree[next] == 0 { // 先修课清零，解锁
                queue = append(queue, next)
            }
        }
    }
    return finished == numCourses
}

pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
    let n = num_courses as usize;
    let mut graph = vec![Vec::new(); n];
    let mut indegree = vec![0; n];
    for p in &prerequisites {
        let (a, b) = (p[0] as usize, p[1] as usize);
        graph[b].push(a); // 先修 b 才能修 a
        indegree[a] += 1;
    }
    let mut queue: std::collections::VecDeque<usize> =
        (0..n).filter(|&i| indegree[i] == 0).collect(); // 没有先修课，直接可修
    let mut finished = 0;
    while let Some(cur) = queue.pop_front() {
        finished += 1;
        for &next in &graph[cur] {
            indegree[next] -= 1;
            if indegree[next] == 0 { // 先修课清零，解锁
                queue.push_back(next);
            }
        }
    }
    finished == n
}

最容易搞反的是建边方向：[a, b] 是“修 a 之前先修 b”，边应当是 b -> a（b 修完才解锁 a），入度加在 a 头上；方向建反了，简单用例照样能过，藏得很深。另外每个节点入度恰好减到 0 时只入队一次，不需要 visited 数组——入度本身就承担了去重。判断依据必须是出队计数 finished == numCourses，而不是“队列空了”：有环时队列也会正常变空，只是环上的课从没进来过。

DFS 三色标记（未访问/访问中/已完成，撞上“访问中”即有环）也能判环，两者复杂度相同；BFS 版的额外好处是出队序列就是一个合法修课顺序，第 210 题“课程表 II”只需把它收集起来返回。

复杂度

指标	复杂度	原因
时间	`O(V + E)`	每个节点入队一次，每条边被松弛一次
空间	`O(V + E)`	邻接表、入度数组和队列

可以迁移的模式

“x 依赖 y”的判定与调度问题，第一步都是建有向图、问有没有环；
Kahn 算法的骨架：入度表 + 零入度队列 + 出队计数，计数不满即有环；
入度减到 0 才入队，天然保证每个点只处理一次，省掉 visited。

任务调度、编译依赖、包管理器装包顺序，内核全是这一套拓扑排序——课程表是它最干净的题面。