Course Schedule
MediumGraphs · Airbnb
There are num_courses courses labelled 0 to num_courses - 1. Each entry prerequisites[i] = [a, b] means you must finish course b before you can take course a.
You take one course at a time. Return True if there is some order in which you can finish all the courses, and False otherwise. That happens exactly when the prerequisites contain a circular dependency, such as 0 needing 1 while 1 needs 0. Courses with no prerequisites can be taken at any time.
Example 1
- Input:
- num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
- Output:
- True
- Explanation
- Take course 0 first, then courses 1 and 2 (both only need 0), then course 3, which needs 1 and 2.
Example 2
- Input:
- num_courses = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]
- Output:
- False
- Explanation
- Course 0 needs 1, 1 needs 2, and 2 needs 0. None of the three can ever be started, so the courses cannot all be finished.
Example 3
- Input:
- num_courses = 5, prerequisites = [[1, 0], [3, 4], [4, 3]]
- Output:
- False
- Explanation
- Courses 0, 1 and 2 are fine, but courses 3 and 4 each need the other first. One circular dependency anywhere is enough to fail.
Constraints
1 <= num_courses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a, b < num_coursesanda != b- All pairs
prerequisites[i]are distinct