Beat 88.88%, 20ms C++ solution using Stack or queue with explanation

  • 0
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> graph(numCourses);
            vector<int> preNum(numCourses, 0);
            stack<int> sq; //DFS
            //queue<int> sq; //BFS, a little bit slow
            int count=0;
            for(auto req : prerequisites)
                //collect all limited courses by req.second
                //number of courses needed to be finished before req.first
            //put avaliable courses in the stack
            for(int i=0; i<numCourses; ++i)
                if(preNum[i]==0) sq.push(i); //avaliable to take
            //start to take course one by one
                //take one course
                int course =;
                //released courses after taking the course                 
                for(auto c : graph[course])
                    //no prerequist, avaliable to take
                    if(--preNum[c]==0) sq.push(c); 
            return count==numCourses;

Log in to reply

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