Topological Sort
LC #207Medium
Course Schedule
Topological Sort
AmazonGoogleMetaBloombergProblem
Determine if you can finish all courses given their prerequisites (detect cycle in directed graph).
graphtopological-sortbfs
Constraints
- ›1 ≤ numCourses ≤ 2000
- ›0 ≤ prerequisites.length ≤ 5000
- ›prerequisites[i] = [a,b] means b must be taken before a
- ›No duplicate edges
Example
Input
numCourses = 2, prerequisites = [[1,0]]Output
trueWhy
Take course 0 first, then course 1. No cycle → can finish