207.课程表（dfs）

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i] 中的所有课程对 互不相同

class Solution { public: bool dfs(int i,vector<vector<int>> &a,vector<int> &v){ if(v[i]==1) return false; if(v[i]==2) return true; v[i]=1; for(auto &x:a[i]){ if(!dfs(x,a,v)){ return false; } } v[i]=2; return true; } bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> a(numCourses); for(auto& p:prerequisites){ a[p[1]].push_back(p[0]); } vector<int> v(numCourses); for(int i=0;i<numCourses;i++){ if(!dfs(i,a,v)){ return false; } } return true; } };

课程依赖关系是有向图

要完成所有课程，必须找到一个顺序，使得每个课程在学习时，其所有先修课程都已完成。

在图论中，这种顺序叫拓扑排序（Topological Sort）。拓扑排序要求图是无环的

v[i] 表示课程 i 的状态：

0：未访问。 1：当前递归路径中正在访问（访问中）。 2：已完成访问（无环）。

如果 v[i] == 1，说明在当前递归路径中再次遇到 i，表示有环，返回 false。

如果 v[i] == 2，说明之前已完成对 i 的访问且无环，无需重复处理，返回 true。

a[i] 是课程 i 的后继课程列表。

使用 for(auto &x:a[i]) 遍历每个后继课程 x。

当所有后继课程都处理完毕，且未发现环，将 v[i] 标记为“已完成”（v[i] = 2）

实例：

输入：numCourses = 4, prerequisites = [[1,0], [2,1], [3,2], [1,3]]

初始化：

a = [[1], [2], [3], [1]]（0 -> 1, 1 -> 2, 2 -> 3, 3 -> 1）v = [0, 0, 0, 0]

i = 0：

v[0] = 0，调用 dfs(0, a, v)： v[0] = 1a[0] = [1]，调用 dfs(1, a, v)： v[1] = 1a[1] = [2]，调用 dfs(2, a, v)： v[2] = 1a[2] = [3]，调用 dfs(3, a, v)： v[3] = 1a[3] = [1]，调用 dfs(1, a, v)： v[1] = 1，发现环，返回 false 返回 false 返回 false 返回 false 返回 false 发现环，返回 false

结果：返回 false（有环，无法完成）。