There are numCourses courses, numbered from 0 to numCourses − 1. Each pair [a, b] in
prerequisites means you must finish course b before you can take course a.
Return true if there is an order in which you can take every course, and false if the
prerequisites make that impossible.
Example 1
- Input
- numCourses = 4, prerequisites = [[2, 0], [2, 1], [3, 2]]
- Output
- true
Example 2
- Input
- numCourses = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]
- Output
- false
Constraints
- 1 ≤
numCourses≤ 2000 prerequisitesholds at most 5000 pairs, each of two different courses, with no pair repeated.
Show the pattern
Topological sort, Graphs
Prerequisites form a directed graph, and every course can be finished exactly when that graph has no cycle. Repeatedly taking a course whose prerequisites are all done (a topological sort) either uses up every course or exposes a loop.
See topological sort in a visualiserShow the approach
Kahn's algorithm. Count each course's prerequisites (its in-degree) and list the courses each one unlocks. Start with every course that has no prerequisites. Repeatedly take one of them, count it as taken, and lower the count of each course it unlocks, adding any that reach 0 to the courses ready to take.
If every course gets taken, the answer is true. A course on a cycle always waits for another
course on the same cycle, so its count never reaches 0; if any course is left over, the answer is
false.
A depth-first search that marks courses as "in progress" and "done", and finds a cycle when it meets an "in progress" course again, works as well.
Time: O(V + E) · Space: O(V + E)