There are numCourses courses labeled 0 to numCourses - 1, and a list of prerequisite pairs where [a, b] means course b must be taken before course a. Return true if every course can be finished — that is, if the prerequisites contain no cycle.
Examples
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: each course requires the other first.
Example 3:
Input: numCourses = 5, prerequisites = [[1,4],[2,4],[3,1],[3,2]]
Output: true
Example 4:
Input: numCourses = 3, prerequisites = []
Output: true
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. Peel Off What Has No Prerequisites Optimal
Intuition
Finishing every course is possible exactly when the prerequisite graph has no cycle. Kahn's algorithm proves it constructively: repeatedly take a course with nothing outstanding and relax its dependents. If every course comes off that way, the order exists; if the process stalls with courses remaining, they are waiting on each other — a cycle. Getting the edge direction right is the usual stumble, so say it out loud: an edge runs from prerequisite to dependent.
Algorithm
1. Build dependents lists and in-degree counts. 2. Queue every course with in-degree zero. 3. Take one, count it, and decrement its dependents; queue any that reach zero. 4. Success when the count reaches numCourses.
Time & Space
Time O(courses + prerequisites). Space O(courses + prerequisites).