C++ Simplicity -post order -


  • 1
    L
    class Solution {
    public:
        vector<int> path;
        bool topsort(int s, vector<vector<int> >& adj, vector<int>& visited )
        {
            if( visited[s] ==  1 ) return false; //got loop
            if( visited[s] ==  2 ) return true;  // already done
            
            visited[s] = 1;  //started
            
            for( auto n : adj[s])
            {
                if(!topsort(n, adj, visited))
                    return false;
            }
            visited[s] = 2;  //done
            path.push_back(s);
            return true;
        }
        
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        
        vector< vector<int> > adj(numCourses);
        
        for( auto e: prerequisites)
        {
            adj[e.first].push_back(e.second);
        }
        vector<int> visited(numCourses, 0);
        
        for( int i=0; i < numCourses; i++)
        {
                if(!topsort(i, adj, visited))
                {
                   return vector<int>();
                }
                    
        }
        return path;
       
    }
    

    };


Log in to reply
 

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