course-schedule-ii.cpp (2072B)
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 // can't cause cycles if no out edges 22 if(edges.find(i) == edges.end()) { 23 if(visited.find(i) == visited.end()) { 24 visited.insert(i); 25 ordering.push_back(i); 26 } 27 } 28 29 if(visited.find(i) != visited.end()) { 30 continue; 31 } 32 33 unordered_set<int> traversedFromStart = {}; 34 35 if (!dfsAcyclic(visited, edges, traversedFromStart, i, ordering)) { 36 return vector<int> {}; 37 } 38 39 } 40 41 std::reverse(ordering.begin(), ordering.end()); 42 return ordering; 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 vector<int>& ordering) { 53 54 if(traversedFromStart.find(current) != traversedFromStart.end()) { 55 return false; 56 } 57 58 for(auto outEdge: edges[current]) { 59 if(visited.find(outEdge) == visited.end()) { 60 traversedFromStart.insert(current); 61 if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge, ordering)) { 62 return false; 63 } 64 } 65 } 66 67 visited.insert(current); 68 ordering.push_back(current); 69 return true; 70 } 71 };