# Easy C++ dfs Solution

• ``````class Solution {
bool isCycle(vector<list<int>>& g, vector<bool>& visited, vector<bool>& rec, int n) {
if(visited[n] == false) {
visited[n] = true;
rec[n] = true;

for(auto iter = g[n].begin(); iter != g[n].end(); ++iter) {
if(isCycle(g, visited, rec, *iter))
return true;
if(rec[*iter])
return true;
}

rec[n] = false;
}

return false;
}

public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<list<int> > g(numCourses, list<int>());
for(int i = 0; i<prerequisites.size(); i++)
g[prerequisites[i].first].push_back(prerequisites[i].second);

vector<bool> visited(prerequisites.size(), false);
vector<bool> rec(prerequisites.size(), false);

for(int i = 0; i<g.size(); i++)
if(isCycle(g, visited, rec, i))
return false;

return true;
}
};``````

• nice solution!

• in function canFinish

vector<bool> visited(prerequisites.size(), false);

vector<bool> rec(prerequisites.size(), false);

should be

vector<bool> visited(numCourses, false);

vector<bool> rec(numCourses, false);

am i right?

• No. The prerequisite vector could contain like this: [1, 0], [2, 0], [3, 0], [2, 1], [3, 2]. In this case, we have 4 courses, but the length of the vector is 5.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.