My Solution With TopoLogical in C++


  • 0
    C

    class Solution {
    public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& pre) {

        stack<int> canAdds;
        vector<unordered_set<int>> graph = make_graph(numCourses,pre);
        vector<int> degrees = get_degrees(numCourses,graph);
        
       
        
        int i=0;
        
        for(auto tmp : degrees){
            if(tmp == 0){
              canAdds.push(i);
              order.push_back(i);
            } 
            ++i;
        }
        
        while(!canAdds.empty()){
            
            int current = canAdds.top();
            canAdds.pop();
            
            for(auto tmp : graph[current]){
                if(!(--degrees[tmp])){
                    canAdds.push(tmp);
                    order.push_back(tmp);
                }
            }
            
        }
        
        vector<int> result;
        
        if(order.size() == numCourses) return order;
        
        return result;
             
        
    }
    
    
    vector<int> get_degrees(int numCourses,vector<unordered_set<int>> graph){
        vector<int> degrees(numCourses,0);
        
        for(int i = 0;i<numCourses;i++){
           
           for(auto tmp : graph[i]){
             degrees[tmp]++;
           }
           
        }
        
        
        return degrees;
    }
    
    vector<unordered_set<int>> make_graph(int numCourses,vector<pair<int,int>> pre){
        
        vector<unordered_set<int>> adj(numCourses);
        
        for(auto tmp : pre){
            adj[tmp.second].insert(tmp.first);
        }
        
        return adj;
    }
    

    private:
    vector<int> order;
    };


Log in to reply
 

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