Course Schedule II (Topological Sort)
Given numCourses and prerequisites, return a valid topological ordering to finish all courses. If impossible, return empty.
Output space-separated order.
Example
Input
4 1:0,2:0,3:1,3:2
Output
0 1 2 3
Reasoning
- The input
4represents the total number of courses, and1:0,2:0,3:1,3:2represents the prerequisites where each course is denoted by a number and its prerequisite is the number after the colon. - We create a graph from the prerequisites: course 0 has no prerequisites, course 1 has 0 as a prerequisite, and course 3 has both 1 and 2 as prerequisites.
- Using topological sort, we start with courses that have no prerequisites (course 0) and add them to the ordering, then remove them from the graph, updating the prerequisites of other courses.
- The updated graph allows us to add course 1 (since 0 is removed), then courses 2, and finally course 3, resulting in a valid topological ordering:
0 1 2 3.
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000