28ms C++ recursive solution with explanation


  • 0
    B
    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;
        } };
    


Log in to reply
 

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