# 28ms C++ recursive solution with explanation

1. Make prerequisites into a graph, where graph[i] = {a, b c...} means that course i has prerequistes of a, b, c and so on.
2. Use visited[i] to track if course i has been visited and use thisPath[i] to see if started from course i, there would be a circle.

``````class Solution {
public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites)
{
if(prerequisites.size() == 0) return true;

//Make it to graph
vector<unordered_set<int>> graph(numCourses);    //Map: graph[course] = {its prerequisites...}
for(auto a : prerequisites)
{
graph[a.second].insert(a.first);
}

//DFS
vector<bool> visited(numCourses, false);     //If the course has been visited.
vector<bool> thisPath(numCourses, false);    //If the course is on current dfs path.
for(int i = 0; i < numCourses; ++i)
{
if(!visited[i] && isCircle(graph, visited, thisPath, i)) return false;
}
return true;
}
bool isCircle(const vector<unordered_set<int>>& graph, vector<bool>& visited, vector<bool>& thisPath, int node)
{
if(visited[node]) return false;
visited[node] = true;
thisPath[node] = true;
for(auto i : graph[node])
{
if(thisPath[i] || isCircle(graph, visited, thisPath, i)) return true;
}
thisPath[node] = false;
return false;
} };
``````

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