题目描述

现在你总共有 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。这是不可能的。

说明

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

提示

1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
3. 拓扑排序也可以通过 BFS  完成。

算法

(DFS拓扑排序) $O(n + m)$

我们可以把n门课程看成n个点，如果课程a依赖于课程b即b是a的先修课之一，我们连一条由a指向b的有向边。这样不指向任何其他点或者指向的点都已经被访问过的点就是没有先修课或者先修课都已经被修完的课程，我们可以利用DFS的性质来找到这样没有出边的点。当我们DFS访问完一个点所有的儿子后就代表我们已经将这门课的先修课给全部修完了，所以我们可以修这门课了。具体思路与分析过程可以参见 LeetCode 210. Course Schedule II 。注意这里我们相当于从低往高给节点编号，即每次DFS访问完一个节点后就将它加入当前修课序列的尾部。

时间复杂度

每个点和边只会被遍历一次，时间复杂度为 $O(n + m)$。

C++ 代码

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        graph = vector<vector<int>>(numCourses);
        for (auto &pre : prerequisites) {
            graph[pre[0]].push_back(pre[1]);
        }

        vis = vector<int>(numCourses, 0);
        for (int i = 0; i < numCourses; i ++ ) {
            if (vis[i] == 0) {
                if (!dfs(i)) return false;
            }
        }
        return true;
    }
private:
    vector<int> vis;
    vector<vector<int>> graph;
    bool dfs(int u) {
        vis[u] = -1;
        for (auto t : graph[u]) {
            if (vis[t] == -1) return false;
            if (vis[t] == 0) {
                if (!dfs(t)) return false;
            }
        }
        vis[u] = 1;
        return true;
    }
};