207. 课程表（dfs）-输入：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] 中的所有课程对 互不相同

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）

实例：