My C++ DFS solution, unordered_map to save the prerequisites and an array to save if a class is already checked

• The unordered_map edges is used to save all the prerequisites of a node. An array, checked, is used to track whether a node is already checked before with the result that no cycle is found (visited[i]==2), or a node is visited already in the current path (visited[i]==1) or it has never been visited (visited[i] ==0). DFS is used to check cycle. If a node with visited = 2 is met, return true (no cycle for that path), if visited =1. then the current path visits a node that is previously visited, i.e. a cycle is detected, return false. If visited = 0, the node is new, then move the path forward.

``````       class Solution {
bool dfs_check(unordered_map<int, vector<int>> &edges, int visited[], int i)
{
if(visited[i] == 1) return false; // a node visited before in the current loop
else if(visited[i] == 2) return true; // checked before and it has no cycle
else
{ // never checked
if(edges.find(i) == edges.end())
{ // if no prerequisite, return true and set the current node visited to 2
visited[i] = 2;
return true;
}
else
{
visited[i] = 1; // indicate the node is visited in the current path
int j;
for(j=0;j<edges[i].size(); j++)
{
if(!dfs_check(edges, visited, edges[i][j])) return false;
}
visited[i] = 2;
return true;
}

}
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(numCourses<=1) return true;
int len = prerequisites.size();
if(len<=0) return true;

int i;
const int n = numCourses;
int visited[n];
std::fill_n(visited, n, 0);
unordered_map<int, vector<int>> edges;

//build the edges table
for(i=0; i<len; i++)
{
if(edges.find(prerequisites[i][0]) == edges.end())
edges[prerequisites[i][0]] = vector<int>(1,prerequisites[i][1]);
else
edges[prerequisites[i][0]].push_back(prerequisites[i][1]);
}

for(i=0; i<n; i++)
{// go through each node, check its prerequisites, if a cycle is found then return false.
if(!dfs_check(edges, visited, i)) return false;
}
return true;
}

};``````

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