Topological order / cycle

Why it matters

Build pipelines, package installers, and course plans must respect prerequisites before work can begin. A dependency cycle leaves every task in that cycle waiting forever, and trying possible schedules can explode into permutations. The decision must account for every course and prerequisite and return False whenever any cycle blocks completion.

numCourses courses labeled 0..n-1. prerequisites[i] = [a, b] means b before a. Return true if you can finish all courses (the graph is a DAG).

Input

numCourses = 5, prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0]]

Output

False

Trying all orders for 5 courses repeats blocked prefixes. For [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0]], only 0 then 4 become available; the queue stops while 1 → 2 → 3 → 1 remains, proving False.

For 5 courses and prerequisites [[1, 0], [2, 1], [3, 2], [1, 3], [4, 0]], draw each edge prerequisite → course. The in-degree array is [0, 2, 1, 1, 1], so only course 0 enters the initial queue.

Taking 0 lowers course 1 to in-degree 1 and course 4 to 0, so 4 joins the queue. Taking 4 unlocks nothing. The queue then empties after 2 courses; 1, 2, and 3 still form a cycle, so taken == 5 is False.