Check Whether a Proposed Course Order Respects Every Prerequisite

Courses are numbered 0 to n - 1, and some courses must be taken before others. Given a proposed order of courses, decide whether it is a valid order in which to take them all.

Function Signature

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

Rules

• Each pair [course, before] in prerequisites means that course before must be taken before course course.
• order is valid when it lists every course from 0 to n - 1 exactly once and, for every pair [course, before], before appears earlier in order than course.
• An order that leaves out a course or lists a course twice is not valid.
• If the prerequisites contain a cycle, no order can be valid, so the answer is False.

Constraints

• 1 <= n <= 10^5
• 0 <= len(prerequisites) <= 10^5
• Each pair holds two different course numbers between 0 and n - 1, and no pair appears twice.
• 0 <= len(order) <= 2 * 10^5, and every value in order is between 0 and n - 1.

Examples

Example 1

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

Course 3 comes before courses 0 and 2, and course 2 comes before course 1.

Example 2

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

Course 1 is placed before its prerequisite, course 2.

Example 3

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

The order satisfies the only prerequisite but never takes course 2.