Asked at

Course Schedule

Medium
VerifiedTopological SortBFSDFS~20 min

You have numCourses courses labeled 0..numCourses - 1. Each pair [a, b] in prerequisites means course b must be taken before course a.

Return true if it is possible to finish every course, false otherwise (a cycle makes it impossible).

The input arrives as a single object { numCourses, prerequisites }.

Examples

in{ numCourses: 2, prerequisites: [[1,0]] }
outtrue

Take course 0 first, then course 1.

in{ numCourses: 2, prerequisites: [[1,0],[0,1]] }
outfalse

Courses 0 and 1 depend on each other, forming a cycle.

Constraints

  • 1 ≤ numCourses ≤ 2000
  • 0 ≤ prerequisites.length ≤ 5000
  • prerequisites[i] = [a, b] means b must be taken before a
  • All prerequisite pairs are distinct.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.