Course Schedule - Medium - L
Published:
Question
- https://leetcode.com/problems/course-schedule/
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Approach
- Cycle detection
Solution
class Solution {
public:
void dfs(vector<vector<int>>& adj, vector<bool> &vis, vector<bool> &rec, int i, bool &ans){
vis[i]=true;
rec[i]=true;
for(int j=0;j<adj[i].size();j++){
if(!vis[adj[i][j]]){
dfs(adj, vis, rec, adj[i][j], ans);
}
if(rec[adj[i][j]]){
ans=false;
}
}
rec[i]=false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int> > adj;
vector<bool> vis;
vector<bool> rec;
for(int i=0;i<numCourses;i++){
vector<int> t;
adj.push_back(t);
vis.push_back(false);
rec.push_back(false);
}
for(int i=0;i<prerequisites.size();i++){
adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
bool ans = true;
for(int i=0;i<numCourses;i++){
if(!vis[i]){
dfs(adj, vis, rec, i, ans);
}
}
return ans;
}
};