algorithms

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

course-schedule.cpp (2037B)

      1 class Solution {
      2 public:
      3     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
      4         // since we can take arbitrarily many courses, we simply have to find
      5         // a cycle in the directed graph of prerequisites.
      6 
      7         // representation of graph:
      8         // [0,1] -> 1 must be completed to take 0. 
      9         // e.g. e = (1,0)
     10 
     11         // we know, based on this requirement:
     12         // 0 <= ai, bi < numCourses
     13         // that all courses are bounded ints in the interval [0,numCourses)
     14 
     15         unordered_map<int,unordered_set<int>> edges = {};
     16 
     17         for(auto edge: prerequisites) {
     18             if (edges.find(edge[1]) != edges.end()) {
     19                 edges[edge[1]].insert(edge[0]);
     20             }
     21             else {
     22                 edges[edge[1]] = unordered_set<int>{edge[0]};
     23             }
     24         }
     25 
     26         unordered_set<int> visited = {};
     27 
     28         for(int i = 0; i < numCourses; ++i) {
     29                         
     30             if(edges.find(i) == edges.end() || visited.find(i) != visited.end()) {
     31                 continue;
     32             }
     33 
     34             unordered_set<int> traversedFromStart = {};
     35             
     36             if (!dfsAcyclic(visited, edges, traversedFromStart, i)) {
     37                 return false;
     38             }
     39 
     40         }
     41 
     42         return true;
     43 
     44         
     45     }
     46 private:
     47     bool dfsAcyclic(
     48         unordered_set<int>& visited, 
     49         unordered_map<int,unordered_set<int>>& edges, 
     50         unordered_set<int>& traversedFromStart,
     51         int current) {
     52 
     53             if(traversedFromStart.find(current) != traversedFromStart.end()) {
     54                 return false;
     55             }
     56 
     57             for(auto outEdge: edges[current]) {
     58                 if(visited.find(outEdge) == visited.end()) {
     59                     traversedFromStart.insert(current);
     60                     if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge)) {
     61                         return false;
     62                     }
     63                 }
     64             }
     65 
     66             visited.insert(current);
     67             return true;
     68         }
     69 };