algorithms

commit c74cdba0592be08f5338a6951bfac3b44efb363e
parent 07429cc6a3d3de2c89091e1281a683802c74b431
Author: Andrew Laack <andrew@laack.co>
Date:   Sun, 23 Aug 2026 11:17:47 -0500

Better top sort approach with 1 less special case

Diffstat:
A
course-schedule-ii/course-schedule-ii-v2.cpp
 | 
63
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 63 insertions(+), 0 deletions(-)
diff --git a/course-schedule-ii/course-schedule-ii-v2.cpp b/course-schedule-ii/course-schedule-ii-v2.cpp
@@ -0,0 +1,63 @@
+class Solution {
+public:
+    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
+                unordered_map<int,unordered_set<int>> edges = {};
+
+        for(auto edge: prerequisites) {
+            if (edges.find(edge[1]) != edges.end()) {
+                edges[edge[1]].insert(edge[0]);
+            }
+            else {
+                edges[edge[1]] = unordered_set<int>{edge[0]};
+            }
+        }
+
+        unordered_set<int> visited = {};
+
+        vector<int> ordering =  {};
+
+        for(int i = 0; i < numCourses; ++i) {
+                
+            if(visited.find(i) != visited.end()) {
+                continue;
+            }
+
+            unordered_set<int> traversedFromStart = {};
+            
+            if (!dfsAcyclic(visited, edges, traversedFromStart, i, ordering)) {
+                return vector<int> {};
+            }
+
+        }
+
+        std::reverse(ordering.begin(), ordering.end());
+        return ordering;
+
+        
+    }
+private:
+    bool dfsAcyclic(
+        unordered_set<int>& visited, 
+        unordered_map<int,unordered_set<int>>& edges, 
+        unordered_set<int>& traversedFromStart,
+        int current,
+        vector<int>& ordering) {
+
+            if(traversedFromStart.find(current) != traversedFromStart.end()) {
+                return false;
+            }
+
+            for(auto outEdge: edges[current]) {
+                if(visited.find(outEdge) == visited.end()) {
+                    traversedFromStart.insert(current);
+                    if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge, ordering)) {
+                        return false;
+                    }
+                }
+            }
+
+            visited.insert(current);
+            ordering.push_back(current);
+            return true;
+        }
+};