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


  • 1
    D

    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;
                }
    
        };

Log in to reply
 

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