There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a.
Return true if you can finish all courses. Return false if the prerequisite graph contains a cycle.
Model the relationships explicitly, then choose BFS, DFS, or union find based on the question. Track visited state so cycles do not create repeated work.
Examples
Input: numCourses = 2, prerequisites = [[1,0]] Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false
Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]] Output: true
Constraints
- 1 <= numCourses <= 2,000
- 0 <= prerequisites.length <= 5,000
- 0 <= a, b < numCourses
- All prerequisite pairs are unique.