题目

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

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

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

题解

这一题的思路参考：

207. 课程表 - 力扣（LeetCode）

解题思路往课程安排图是否是有向无环图（DAG）那边去靠。那么便可以用拓扑排序的方法来解决了：对DAG的顶点进行排序，对每条有向边（u, v），均有u（在排序记录中）比v先出现。或者说对于某个点v，只有v的源点都出现了，v才出现。

法一： 入度表（广度优先搜索）

算法流程：

  1. 统计课程安排表里每个节点的入度，并且生成入读表indegrees
  2. 用队列queue，把所有入度为0的节点入队；
  3. 当queue非空，依次把队首节点出队，然后在课程安排图中删除该节点pre（把该节点对于所有邻接节点cur的入度设置为-1，indegrees[cur] -= 1，入度为-1表示cur的所有前驱节点被删除了，然后把cur入队）
  4. 每次pre出队时，执行numCourses--；如果课程安排图是有向无环图（可安排），那么所有节点都入队并且出队过，完成了拓扑排序。如果存在环的话，一定有节点的入度始终不为0。所以拓扑排序的出队次数等于课程个数，返回numCourses == 0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        // 入度表
        List<List<Integer>> adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        // Get the indegree and adjacency of every course.
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        // Get all the courses with the indegree of 0.
        for (int i = 0; i < numCourses; i++)
            if (indegrees[i] == 0)
                queue.add(i);
        // BFS TopSort.
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for (int cur : adjacency.get(pre))
                if (--indegrees[cur] == 0)
                    queue.add(cur);
        }
        return numCourses == 0;
    }
}

法二：深度优先搜索

思想为通过DFS判断是否有环

算法流程：

  1. 借助一个标志列表flags，判断每个节点i的状态：i == 0，未被访问、i == 1被当前节点启动的DFS访问、i == -1被其他节点启动的DFS访问
  2. 对numCourses个节点依次执行DFS，判断每个节点起步DFS是否有环，有直接返回false。

DFS流程：

  1. 终止条件：

    • flag[i] == -1 当前访问节点已经被其他节点启动的DFS访问了，不需要再进行搜索，返回true
    • flag[i] == 1，本轮DFS节点i被第二次访问了，有环，返回false

  2. 将当前访问节点i对应flag[i]置1，标记访问过；

  3. 递归访问当前节点i的所有邻接节点j，有环返回false

  4. 若当前节点的所有邻接节点都被遍历没环，flag[i] = -1，返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        int[] flags = new int[numCourses];
        for (int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);
        for (int i = 0; i < numCourses; i++)
            if (!dfs(adjacency, flags, i))
                return false;
        return true;
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if (flags[i] == 1)
            return false;
        if (flags[i] == -1)
            return true;
        flags[i] = 1;
        for (Integer j : adjacency.get(i))
            if (!dfs(adjacency, flags, j))
                return false;
        flags[i] = -1;
        return true;
    }
}