28ms C++ recursive solution with explanation

  • 0
    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 {
        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)
            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.