algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

course-schedule-ii-v2.cpp (1797B)

      1 class Solution {
      2 public:
      3     vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      4                 unordered_map<int,unordered_set<int>> edges = {};
      5 
      6         for(auto edge: prerequisites) {
      7             if (edges.find(edge[1]) != edges.end()) {
      8                 edges[edge[1]].insert(edge[0]);
      9             }
     10             else {
     11                 edges[edge[1]] = unordered_set<int>{edge[0]};
     12             }
     13         }
     14 
     15         unordered_set<int> visited = {};
     16 
     17         vector<int> ordering =  {};
     18 
     19         for(int i = 0; i < numCourses; ++i) {
     20                 
     21             if(visited.find(i) != visited.end()) {
     22                 continue;
     23             }
     24 
     25             unordered_set<int> traversedFromStart = {};
     26             
     27             if (!dfsAcyclic(visited, edges, traversedFromStart, i, ordering)) {
     28                 return vector<int> {};
     29             }
     30 
     31         }
     32 
     33         std::reverse(ordering.begin(), ordering.end());
     34         return ordering;
     35 
     36         
     37     }
     38 private:
     39     bool dfsAcyclic(
     40         unordered_set<int>& visited, 
     41         unordered_map<int,unordered_set<int>>& edges, 
     42         unordered_set<int>& traversedFromStart,
     43         int current,
     44         vector<int>& ordering) {
     45 
     46             if(traversedFromStart.find(current) != traversedFromStart.end()) {
     47                 return false;
     48             }
     49 
     50             for(auto outEdge: edges[current]) {
     51                 if(visited.find(outEdge) == visited.end()) {
     52                     traversedFromStart.insert(current);
     53                     if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge, ordering)) {
     54                         return false;
     55                     }
     56                 }
     57             }
     58 
     59             visited.insert(current);
     60             ordering.push_back(current);
     61             return true;
     62         }
     63 };