MediumPythonJavaScriptTypeScript
Graph — Course Schedule (Cycle Detection)
Data StructuresGraphsTopological SortBFS
solve(numCourses, prerequisites) — there are numCourses courses numbered0..numCourses-1. Each pair [a, b] in prerequisites means you must take
course b before course a. Return true if you can finish every course.
That is exactly the question "does this directed graph have a cycle?" — a
cycle of prerequisites makes the schedule impossible. Use Kahn's algorithm: keep
removing courses with no remaining prerequisite and count how many you can remove.
Examples
solve(2, [[1,0]]) → true
solve(2, [[1,0],[0,1]]) → false
solve(3, [[1,0]]) → true // course 2 is independent
solve(3, [[0,1],[1,2],[2,0]]) → falseSample tests
Test #1Simple chain
Input: [2,[[1,0]]]
Output: true
Test #2Two courses require each other
Input: [2,[[1,0],[0,1]]]
Output: false
Test #3No prerequisites
Input: [1,[]]
Output: true