codejump
MediumPythonJavaScriptTypeScript

Graph — Course Schedule (Cycle Detection)

Data StructuresGraphsTopological SortBFS

solve(numCourses, prerequisites) — there are numCourses courses numbered
0..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]]) → false

Sample 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