My simple c++ solution. similar to course schedule I


  • 0
    K
    class Solution {
    public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int>course[numCourses];
        stack<int>stack;
        vector<int>res;
        for(auto & e : prerequisites){
            course[e.second].push_back(e.first);
        }
        vector<bool>current(numCourses, false);
        vector<bool>visited(numCourses, false);
        for(int i=0; i < numCourses ;i++){
            if(!visited[i] && !helper(course, current, visited, stack, i))return {};
        }
        while(!stack.empty()){
            res.push_back(stack.top());
            stack.pop();
        }
        return res;
    }
    
    bool helper(vector<int>course[], vector<bool>& current, vector<bool>& visited, stack<int>& stack, int i){
        current[i]=true;
        for(auto & x: course[i]){
            if(current[x] || !helper(course, current, visited, stack, x))return false;
        }
        current[i]=false;
        if(!visited[i])stack.push(i);
        visited[i]=true;
        return true;
    }
    };

Log in to reply
 

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