Course Schedule Can Finish

Detect cycles in a prerequisite graph to see if all courses can be completed.

graph cycle topological dfs bfs

You are given a list of courses labeled from 0 to numCourses - 1. You are also given a list prerequisites where each element is a pair [a, b], meaning that to take course a you must first complete course b (i.e., b is a prerequisite of a).

Write a function `can_finish(numCourses: int, prerequisites: list[list[int]]) -> bool` that returns True if it is possible to finish all courses, and False otherwise. This is equivalent to checking whether the directed graph of prerequisites has a cycle.

You may assume all course labels are between 0 and numCourses - 1. There are no duplicate prerequisite pairs.

Constraints

0 <= numCourses <= 2000
0 <= len(prerequisites) <= 5000
Each prerequisite pair has 0 <= a, b < numCourses.
Your solution should run in O(numCourses + len(prerequisites)) time.

Example

>>> can_finish(2, [[1, 0]])
True
>>> can_finish(2, [[1, 0], [0, 1]])
False
>>> can_finish(3, [[0, 1], [1, 2]])
True

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the prerequisites as a directed graph where an edge from b to a means b must be taken before a.

A cycle in this graph means it's impossible to finish all courses.

You can use DFS with three states (unvisited, visiting, visited) to detect cycles.

Alternatively, compute the in-degree of each course and repeatedly remove courses with in-degree 0 (Kahn's algorithm). If you can remove all courses, there is no cycle.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.