← 返回 netflix 的题目列表Topological Sort Problem
类型:online_judge
Given a directed acyclic graph representing the prerequisite relationship of courses, find an order to complete all courses as required. If course A is a prerequisite of course B, A must be earlier in the sequence than B. Implement a function findOrder(numCourses, prerequisites) to return a valid course order.
Input numCourses is an integer indicating the number of courses, prerequisites is a list where each element is a list of two integers representing a prerequisite relationship where the first integer is the course and the second is the prerequisite.
Example
Input:
numCourses = 2,
prerequisites = [[1,0]]
Output: [0,1]
Input:
numCourses = 4,
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Constraints
Number of courses is in the range [1, 2000]
Number of prerequisites will not exceed numCourses * (numCourses - 1)
Note: If there is no possible course order, return an empty list.
Example
Input
2
[[1,0]]