関小君刷题记

题目大意：

课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:

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

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=207

解题思路分析：

这是一道中等难度的题目。普通的dfs思路完全可以搞定。之所以此题要发博客分析一下，原因在于本题的dfs可以植入拓扑排序（Topological Sorting）的思想，来更加方便的解题。同时也为了本题目的续集-《课程表2》做准备。

续集文章看这里：LEETCODE 210. COURSE SCHEDULE II解题思路分析

先简单说下拓扑排序，拓扑排序通常用来“排序”具有依赖关系的任务。 比如本题的例子，如果想修课程1，就必须先修完课程0。故在这个课程任务中，任意两个课程要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

因此，回到本题，对于是否能够完成所有课程的学习，也就是求所有课程是否能够满足拓扑排序。

实现拓扑排序的框架基本上是dfs深度优先搜索的写法，此外我们还需要引入一个visited[]数组，表示每一个节点的状态。其中visited[i]的值：

・ 0 代表还未访问的状态
・ 1 代表正在访问的状态
・ 2 代表已经访问完成

如果一个节点还未被访问过，则他是可以访问的，进而递归查看其后续节点（也就是本题中对应当前课程的所有先修课）。

如果当前访问节点的状态为1，说明该节点正在递归访问其后续节点，此时再次回到当前节点时，只能说明递归访问路径出现了环路（比如课程A的先修课是B，此时A的状态为1，递归到B时发现其先修课为A，再递归到A时发现其状态为1，这就是回路。），这是不能满足条件的情况，可以直接返回false。

如果状态为2，则说明当前节点的所有后续路径已经遍历（递归）完成，符合拓扑排序的条件，这时再访问到此节点，可以直接返回true。（比如我们知道课程A的先修课是B，而B没有先修课要求，这时A到B之间是满足条件的，因此A和B的状态都可以更新为2。接下来出现了一门课程C，其先修课为A，因为A的转态是2，所以我们可以清楚的直到A，B，C之间没有回路）

看下本题的完整代码：

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 为了将prerequisites转化为图结构，定义一个graph数组。
    // graph下标代表课程编号，值代表该课程所有先修课列表。
    List<Integer>[] graph = new ArrayList[numCourses];
    // 初始化graph
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList<>();
    }
    // 将prerequisites转化为图结构。
    for (int[] prerequisite : prerequisites) {
        graph[prerequisite[0]].add(prerequisite[1]);
    }
    // 创建一个visited 数组
    // 0: unvisited; 1: visiting 2: visited
    int[] visited = new int[numCourses];
    // 循环每一节课
    for (int i = 0; i < numCourses; i++) {
        // dfs递归该课的先修课路径上是否存在回路。
        if (!dfs(graph, i, visited)) {
            // 如果存在回路可直接返回false。
            return false;
        }
    }
    return true;
}
// 返回true代表没有回路，false代表发现回路 
private boolean dfs(List<Integer>[] graph, int currentCourse, int[] visited) {
    // visited状态为1表示发现回路，返回false
    if (visited[currentCourse] == 1) {
        return false;
    }
    // visited状态为2表示当前节点之后不存在回路，可直接返回true
    if (visited[currentCourse] == 2) {
        return true;
    }
    // 开始递归当前节点的先修课
    // 将状态更新为1
    visited[currentCourse] = 1;
    // 循环当前课的所有先修课
    for (int preCourse : graph[currentCourse]) {
        // 递归查看先修课之后的路径是否有回路
        if (!dfs(graph, preCourse, visited)) {
            // 如果有回路直接返回false。
            return false;
        }
    }
    // 当前节点的所有先修课路径循环结束后，将visited更新为2。
    visited[currentCourse] = 2;
    return true;
}

本解法执行时间为2ms

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-207-course-schedule解题思路分析/