- Make prerequisites into a graph, where graph[i] = {a, b c...} means that course i has prerequistes of a, b, c and so on.
- 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;
} };
```