Course Schedule II

Given numCourses and prerequisite pairs, return one valid order to finish all courses. Return an empty array if no valid order exists. Pattern focus: Kahn's Algorithm. Topological ordering with indegrees and a queue is the standard solution.

Input Format

numCourses = course count, prerequisites = prerequisite pairs [course, prerequisite]

Output Format

a valid topological order or an empty array

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9

Examples

Example 1:

Input:

numCourses = 2
prerequisites = [[1,0]]

Output:

[0,1]

Example 2:

Input:

numCourses = 2
prerequisites = [[1,0],[0,1]]

Output:

[]

Example 3:

Input:

numCourses = 1
prerequisites = [[0,0]]

Output:

[]

Example 4:

Input:

numCourses = 3
prerequisites = [[1,0],[2,1]]

Output:

[0,1,2]

Example 5:

Input:

numCourses = 3
prerequisites = [[0,1],[0,2],[1,2]]

Output:

[2,1,0]

Example 6:

Input:

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output:

[0,1,2,3]
Loading...
Course Schedule II - Topological Sort