class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
if (!prerequisites.size()) return true;
vector<vector<int> > map(numCourses, vector<int>());
for(int i = 0; i < prerequisites.size(); i++) {
map[prerequisites[i].first].push_back(prerequisites[i].second);
}
vector<bool> isVisited(numCourses, false);
for(int j = 0; j < numCourses; j++) {
if (!isVisited[j]) {
vector<bool> onStack(numCourses, false);
if (hasCycle(map, j, isVisited, onStack)) {
return false;
}
}
}
return true;
}
bool hasCycle(vector<vector<int> >& map, int j, vector<bool>& isVisited, vector<bool> &onStack) {
isVisited[j] = true;
onStack[j] = true;
for(int k: map[j]) {
if (onStack[k]) {
return true;
} else {
if (hasCycle(map, k, isVisited, onStack)) {
return true;
}
}
}
onStack[j] = false;
return false;
}
};