Course Schedule

Medium· Topological Sort· Cycle Detection

Problem

There are numCourses courses labelled 0 to numCourses - 1, and prerequisites[i] = [a, b] means b must be taken before a. Decide whether it is possible to finish every course.

Examples

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

Output: true

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

Output: false

Each course requires the other, forming a cycle.

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• All pairs are distinct

Hints & approach

Hint 1

Model courses as nodes and prerequisites as directed edges.

Hint 2

You can finish everything exactly when the graph has no cycle.

Hint 3

Kahn's algorithm: repeatedly take courses with zero remaining prerequisites.

Approachtry the hints first

Build an adjacency list from b to a and an in-degree array. Enqueue all courses with in-degree 0. Pop a course, count it as taken, and decrement the in-degree of each course it unlocks, enqueuing any that drop to 0. If the number taken equals numCourses the graph is acyclic and the answer is true. A DFS with three colors (unvisited, visiting, done) detecting back edges is an equivalent approach.

Time O(V + E) · Space O(V + E)

← PreviousRotting Oranges Next →Course Schedule II