Course Schedule II
Medium · topological sort
A college offers num_courses courses, numbered 0 to num_courses - 1. You take them one at a time. Some courses have requirements, given as a list prerequisites of pairs [course, pre]: course pre must be finished before you start course. The same pair may appear more than once.
You want a plan that takes every course exactly once. Many plans can be valid, so the one you must return is fixed by a rule: at each step, take the course with the smallest number among all the courses you are currently allowed to take (those not yet taken whose required courses are all taken).
Return the courses in the order you take them. If no plan can finish every course, return an empty list.
Examples
Example 1
Input: num_courses = 4, prerequisites = [[0, 2], [1, 3]]
Output: [2, 0, 3, 1]
At first only 2 and 3 are allowed, and 2 is smaller. Then 0 and 3 are allowed, so 0 comes next, then 3, then 1.
Example 2
Input: num_courses = 3, prerequisites = [[1, 2], [0, 1]]
Output: [2, 1, 0]
Each course unlocks the next one, so only one order is possible.
Example 3
Input: num_courses = 3, prerequisites = [[1, 0], [2, 1], [1, 2]]
Output: []
Courses 1 and 2 each need the other first, so neither can ever be taken.
Constraints
- 1 <= num_courses <= 1000
- 0 <= len(prerequisites) <= 5000
- Each pair holds two course numbers in the range 0 to num_courses - 1. The two numbers of a pair may be equal.