Check Whether Every Course Can Be Completed Under Prerequisite Rules

There are n courses, labeled 0 to n - 1. Each pair [a, b] in prerequisites means that course b must be completed before course a can be taken. Courses are taken one at a time, and each course is taken once.

Return True if it is possible to complete all n courses while respecting every prerequisite, and False otherwise.

Function Signature

def can_finish_all(n: int, prerequisites: list[list[int]]) -> bool:

Rules

• A course can be taken only after every course it depends on has been completed.
• The answer is True exactly when some order of all n courses, with each course appearing once, places b before a for every pair [a, b]. Otherwise the answer is False.
• A course that appears in no pair has no prerequisites and can be taken at any time.
• If even one course can never be completed, the answer is False, even when every other course can be completed.

Constraints

• 1 <= n <= 2000
• 0 <= len(prerequisites) <= 5000
• Each pair is [a, b] with 0 <= a < n, 0 <= b < n and a != b.
• No pair appears more than once.

Examples

Example 1

Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: True

Courses 1 and 2 each need course 0, and course 3 needs both 1 and 2. Taking the courses in the order 0, 1, 2, 3 respects every pair.

Example 2

Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]
Output: False

Course 0 needs 1, course 1 needs 2, and course 2 needs 0, so none of them can be taken first.

Example 3

Input: n = 5, prerequisites = [[1, 0], [2, 1], [3, 4], [4, 3]]
Output: False

Courses 0, 1 and 2 can be taken in that order, but course 3 needs 4 and course 4 needs 3, so neither of those two can ever be taken.