Course Schedule

Given numCourses and prerequisite pairs, return true if it is possible to finish all courses. Pattern focus: Kahn's Algorithm. This is the classic BFS topological-sort feasibility check.

Input Format

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

Output Format

true if all courses can be completed

Constraints

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

Examples

Example 1:

Input:

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

Output:

true

Example 2:

Input:

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

Output:

false

Example 3:

Input:

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

Output:

true

Example 4:

Input:

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

Output:

true

Example 5:

Input:

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

Output:

false

Example 6:

Input:

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

Output:

true
Loading...
Course Schedule - Topological Sort DSA Problem