课程表 | echo

207. 课程表

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

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

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

提示：

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

此题可以看作判断一个有向图是否存在环，如果图中存在环，则不存在拓扑排序。如果图中不存在环，则可能存在不止一种拓扑排序。

不存在拓扑排序：

存在拓扑排序：

上图中存在拓扑排序中的一种为：[0, 2, 1, 3, 5, 6, 4]。

求拓扑序列方法：不断取下「入度」为零的结点直到图中没有结点或没有入度为零的结点，按取下结点的顺序就得到了拓扑排序。

边缘列表就是存储图的每一条边， [[1,0]]代表存在一条结点 0 到结点 1 的边。

方法一：BFS

我们首先统计每个结点的出边信息和入度信息，首先将入度为零的结点加入队列，取下一个结点，并将该结点所指向的结点入度减一，同时将入度减为零的结点加入队列，不断重复这个步骤直到队列为空，取下结点的顺序就是拓扑排序。

class Solution {
    List<List<Integer>> edges;//edges[i] 为结点 i 所指向的结点数组
    int[] indeg;//indeg[i]为结点 i 的入度

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for(int i = 0; i < numCourses; i++){
            edges.add(new ArrayList<Integer>());
        }

        indeg = new int[numCourses];
        for(int[] edge : prerequisites){
            //存在 edge[1] 到 edge[0] 的边，把edge[0] 加入到 edge[1]
            edges.get(edge[1]).add(edge[0]);
            //edge[0] 入度加一
            ++indeg[edge[0]];
        }

        //queue 存储入度为 0 的结点
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(indeg[i] == 0){
                queue.offer(i);
            }
        }
		//visited 记录已经取下的结点个数
        int visited = 0;
        while(!queue.isEmpty()){
            ++visited;
            //取下一个入度为 0 的结点
            int u = queue.poll();
            //将该结点所指向的结点的入度减一
            for(int v : edges.get(u)){
                --indeg[v];
                //将入度为 0 的结点加入队列
                if(indeg[v] == 0){
                    queue.offer(v);
                }
            }
        }
        //能取下所有结点则存在拓扑排序
        return visited == numCourses;
    }
}

时间复杂度 O(n+m)，其中 n 为课程数，m 为先修课程的要求数。空间复杂度 O(n+m)。

方法二：DFS

我们也可以使用深度优先搜索来找到拓扑排序，我们使用一个栈来存储拓扑排序。对于任意一个结点，我们首先访问该结点，继续访问该结点指向的结点，一直递归地进行这个操作，直到当前访问的结点出度为 0 ，就开始递归返回，在返回的过程中将结点加入栈中。对所有未搜索过的结点进行深度优先搜索，最后得到的栈中，从栈顶到栈底就是拓扑排序。

对于图中的任意结点有三个状态：

未搜索，还没有搜索到这个结点；
搜索中，已经搜索过这个结点，还未回溯到该结点，此时这个结点还没有入栈；
已完成，已经搜索过这个结点，已经将该结点入栈。

每一轮深度优先搜索开始时，我们选择一个未搜索过的结点。

算法流程：

将当前搜索的结点 u 标记为搜索中，遍历该结点所指向的每一个结点 v
- 如果 v 为未搜索，那么开始搜索 v，等待回溯到 u；
- 如果 v 为搜索中，那么图中存在一个环，不存在拓扑序列；
- 如果 v 为已完成，v 已经在栈中，u 还不在栈中，满足栈中 u 在 v 的上方，不用操作。
当 u 所指向的所有结点都为已完成时，将 u 放入栈中，将其标为已完成。

由于我们不需要拓扑序列，只用判断它是否存在，我们只用一个布尔值来代替栈。

class Solution {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for(int i = 0; i < numCourses; i++){
            edges.add(new ArrayList<Integer>());
        }
		//visited[i] 为结点 i 的状态，0 代表未搜索，1 代表搜索中，2 代表已完成
        visited = new int[numCourses];
        for(int[] edge : prerequisites){
            edges.get(edge[1]).add(edge[0]);
        }
		//拓扑序列存在时搜索
        for(int i = 0; i < numCourses && valid; i++){
            //不断选取未搜索的结点进行 DFS
            if(visited[i] == 0){
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int u){
        //将当前结点 u 状态改为 搜索中
        visited[u] = 1;
        //选取 u 所指向的结点进行 DFS
        for(int v : edges.get(u)){
            //u 指向的结点 v 未搜索过，递归地搜索
            if(visited[v] == 0){
                dfs(v);
                //搜索过程中出现环，返回
                if(!valid){
                    return;
                }
            }else if(visited[v] == 1){//存在环，将 valid 设为false，返回
                valid = false;
                return;
            }
        }
        //将结点 u 设为已完成状态
        visited[u] = 2;
    }
}

时间复杂度 O(n+m)，其中 n 为课程数，m 为先修课程的要求数。空间复杂度 O(n+m)。