Topological Sort
LC #210Medium
Course Schedule II
Topological Sort
AmazonGoogleMetaBloombergUberProblem
Return the order in which to take courses to finish all of them.
graphtopological-sortbfs
Constraints
- ›1 ≤ numCourses ≤ 2000
- ›0 ≤ prerequisites.length ≤ numCourses × (numCourses − 1)
- ›Return [] if impossible (cycle detected)
Example
Input
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Output
[0,2,1,3] or [0,1,2,3]Why
Multiple valid orderings exist. Return any valid topological order