Easy to understand topological sort


  • 0
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> result;
            vector<set<int> > graph(numCourses), reverseGraph(numCourses);
            vector<bool> visitedCourses(numCourses, false);
    
            for (auto& edge : prerequisites) {
                graph[edge.first].insert(edge.second);
                reverseGraph[edge.second].insert(edge.first);
            }
    
            // set with courses ready to be taken
            set<int> ready;
            for (int course = 0; course < numCourses; ++course) 
                if (graph[course].empty()) 
                    ready.insert(course);
    
            while (!ready.empty()) {
                int course = *ready.begin();
                visitedCourses[course] = true;
                result.push_back(course);
                for (auto dependant : reverseGraph[course]) {
                    graph[dependant].erase(course);
                    if (graph[dependant].empty() && !visitedCourses[dependant]) {
                        ready.insert(dependant);
                        visitedCourses[dependant] = true;
                    }
                }
                ready.erase(course);
            }
            return result.size() != numCourses 
                ? vector<int>() 
                : res;
        }
    };
    

Log in to reply
 

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