课程表

BraumAce2024年8月3日约 712 字大约 2 分钟

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 $prerequisites[i] = [a_i, b_i]$ ，表示如果要学习课程 $a_i$ 则必须先学习课程 $b_i$ 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路

判断条件：当存在循环依赖的时候，无法完成所有课程。

比如：prerequisites = [[1,0],[0,1]]，在学习课程 1 之前，需要先完成课程 0 ；并且学习课程 0 之前，还应先完成课程 1 。产生了循环依赖，所以不可能完成所有课程。

所以，我们可以把题目的输入转化成一幅有向图，然后再判断图中是否存在环。

使用邻接表建图：

List<Integer>[] g;

List<Integer>[] buildGraph(int n, int[][] edges) {
    // 图中共有 n 个节点
    List<Integer>[] graph = new LinkedList[nu];
    for (int i = 0; i < n; i++) {
        g[i] = new LinkedList<>();
    }
    for (int[] edge : edges) {
        int from = edge[1], to = edge[0];
        // 添加一条从 from 指向 to 的有向边
        g[from].add(to);
    }
    return g;
}

接下来，遍历建好的图。

要注意到图中并不一定所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索，用数组 st 标记所有走过的点，用数组 onPath 标记当前节点搜索时遍历过的节点，即路径节点，在搜索完当前所能走到的所有节点后，回退状态，以便给其他节点搜索。

在一次搜索中，只要发现该节点已经被 onPath 标记了，表示回到了起点，成了一个环，那么就不满足条件，返回 false，否则返回 true。

代码

class Solution {
    boolean onPath[];  // 记录一次DFS经过的节点
    boolean st[];  // 记录遍历过的节点
    boolean hasCycle = false;  // 记录图中是否有环

    void dfs(List<Integer>[] g, int x) {
        if (onPath[x]){
            hasCycle = true;  // 如果当前节点走过了，表示出现了环
        }

        // 如果找到了环，就不用遍历了
        if (st[x] || hasCycle) return;

        st[x] = true;
        onPath[x] = true;  // 标记走过
        for (int t : g[x]){
            dfs(g, t);     // 递归遍历
        }
        onPath[x] = false;  // 恢复现场
    }

    // n为选修课程数，edges为先修课程关系
    public boolean canFinish(int n, int[][] edges) {
        st = new boolean[n];
        onPath = new boolean[n];

        // 邻接表建图 g[a] -> b
        List<Integer>[] g = new LinkedList[n];
        for (int i = 0; i < n; i++) g[i] = new LinkedList<>();
        for (int[] edge : edges){
            int from = edge[1];
            int to = edge[0];
            g[from].add(to);
        }

        for (int i = 0; i < n; i++){
            dfs(g, i);
        }

        return !hasCycle;
    }
}

课程表

课程表

题意

思路

代码