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;
}
};