Course Schedule — Can All Courses Be Finished?

Baseline Graphs · Topo Sort Problems O(N + E) · O(N + E)

The Training-Pass Feasibility Check

A certification body offers numbered training passes, some of which require earlier passes first. Each requirement is one-way: pass A demands pass B beforehand. Before publishing the term plan, the registrar must confirm no circular requirement chain makes the whole program impossible to complete.

Input: An integer numCourses and a list prerequisites where each pair [a, b] means course b must be taken before course a.

Output: Return true if all courses can be completed in some order, otherwise false.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
All prerequisite pairs are unique

Examples

Example 1

Input: {"numCourses":2,"prerequisites":[[1,0]]}
Output: true
Take 0 first, then 1 — no conflict.

Example 2

Input: {"numCourses":2,"prerequisites":[[1,0],[0,1]]}
Output: false
Each course demands the other first — an impossible circular requirement.

Solve this in your browser →

Also on LeetCode ↗