Dependencies form a directed graph: an edge b -> a means b must come before a. You can finish everything exactly when that graph has no cycle. Kahn's algorithm finds out by repeatedly removing nodes that have nothing left to wait for.
There are num_courses courses labelled 0 .. num_courses-1. You are given prerequisites where [a, b] means you must take course b before course a. Return True if it is possible to finish all courses, otherwise False.
Examples
Input: num_courses = 2, prerequisites = [[1, 0]]
Output: True
Explanation: take 0 then 1
Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False
Explanation: 0 needs 1 and 1 needs 0
Constraints
1 <= num_courses <= 20000 <= len(prerequisites) <= 5000, no duplicate pairs- Target: O(V + E) time
Goals
- Model prerequisites as a directed graph
- Detect a cycle in a directed graph with Kahn's algorithm (in-degree counting)
- Recognise that a topological order exists if and only if the graph is acyclic