LeetCode HOT100系列题解之课程表（9/100）

 一、题目 

         课程表. - 力扣（LeetCode）

 二、题目解析        

          想要学习课程Bi，那么就要学习课程Ai，一个前后关系，比较好表示前后关系的就是建图。如果在学A课之前要学B课，学B课之前又要学A课，那么实际上构成了环，因此比较好想到的就是建图后DFS找环。

三、题目代码

class Solution {
public:static const int N = 5010;vector<int> vec[N];int color[N];bool dfs(int u){color[u] = 0;for(int v : vec[u]){if(color[v] == 0) {return false;}else if(color[v] == -1){if(!dfs(v))return false;}}color[u] = 1;return true;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int n = prerequisites.size();for(int i = 0; i < n; i ++)vec[prerequisites[i][1]].push_back(prerequisites[i][0]);memset(color, -1, sizeof color);for(int i = 0; i < numCourses; i ++){if(color[i] == -1){if(!dfs(i))return false;}}return true;}
};