There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Solution: (Cycle Detection in Directed Graph)
Using 3 colours/DFS
class Solution
{
public:
bool dfs(int node, vector<int> v[], vector<int> &colr)
{
colr[node] = 1;
for (int i = 0; i < v[node].size(); i++)
{
if (colr[v[node][i]] == 1)
{
return true;
}
if (colr[v[node][i]] == 0)
{
if (dfs(v[node][i], v, colr))
{
return true;
}
}
}
colr[node] = 2;
return false;
}
bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
{
vector<int> v[numCourses];
vector<int> colr(numCourses, 0);
for (int i = 0; i < prerequisites.size(); i++)
{
v[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
for (int i = 0; i < numCourses; i++)
{
if (colr[i] == 0)
{
if (dfs(i, v, colr))
{
return false;
}
}
}
return true;
}
};