210. Course Schedule II

[namespace-io]

class Solution {
public:
    
    bool acyclic(vector<vector<int>>& v, vector<bool>& todo, vector<bool>& done, int node, vector<int>& order){
        if(todo[node]) return false;
        if(done[node]) return true;
        
        todo[node] = true;
        done[node] = true;     
        for(auto next : v[node]){
            if(!acyclic(v, todo, done, next, order)) return false;

        }
        
        order.push_back(node);
        todo[node] = false;
        return true;
    }

    
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> v(numCourses, vector<int>());
        vector<bool> todo(numCourses, false);
        vector<bool> done(numCourses, false);
       
       
        for(auto p : prerequisites){
            v[p[1]].push_back(p[0]);
        }
        
        vector<int> order;
        
        for(int i = 0; i < numCourses; i++){
            if(!done[i] && !acyclic(v, todo, done, i, order)) return vector<int>();
        }
        
       
        
      
        
       reverse(order.begin(), order.end());
      
        
        return order;
    }
};

class Solution {
public:
    
    bool acyclic(vector<vector<int>>& v, vector<bool>& todo, vector<bool>& done, int node){
        if(todo[node]) return false;
        if(done[node]) return true;
        
        todo[node] = true;
        done[node] = true;     
        for(auto next : v[node]){
            if(!acyclic(v, todo, done, next)) return false;

        }
        
        
        todo[node] = false;
        return true;
    }
    
    void toposort(vector<vector<int>>& m, vector<bool>& visit, vector<int>& order, int i){
        if(!visit[i]){
            for(auto prev : m[i]){
                if(!visit[prev]){
                    toposort(m, visit, order, prev);
                }
            }

            order.push_back(i);
            visit[i] = true;
        }
        
    }
    
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> v(numCourses, vector<int>());
        vector<bool> todo(numCourses, false);
        vector<bool> done(numCourses, false);
       
       
        for(auto p : prerequisites){
            v[p[1]].push_back(p[0]);
        }
        for(int i = 0; i < numCourses; i++){
            if(!done[i] && !acyclic(v, todo, done, i)) return vector<int>();
        }
        
        
        vector<vector<int>> m(numCourses, vector<int>());
        vector<bool> visit(numCourses, false);
        for(auto p : prerequisites){
            m[p[0]].push_back(p[1]);
        }
        
        vector<int> order;
        for(int i = 0; i < numCourses; i++){
            if(v[i].size() == 0) {
                // cout << i <<endl;
                toposort(m, visit, order, i);
            }
        }
        
        return order;
    }
};