There are a total of
numCourses courses you have to take, labeled from
numCourses - 1. You are given an array
prerequisites[i] = [ai, bi] indicates that you must take course
bi first if you want to take course
- For example, the pair
[0, 1], indicates that to take course
0you have to first take course
true if you can finish all courses. Otherwise, return
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
- All the pairs prerequisites[i] are unique.
Use topological sort to keep appending the course with indegree 0 to the queue. In the end, check how many number of courses can be taken.
class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: adjacency_list =  indegrees =  for i in range(numCourses): adjacency_list.append() indegrees.append(0) for prerequisite in prerequisites: adjacency_list[prerequisite].append(prerequisite) indegrees[prerequisite] += 1 queue =  for i, indegree in enumerate(indegrees): if indegree == 0: queue.append(i) count = 0 while queue: course = queue.pop(0) count += 1 for adj_course in adjacency_list[course]: indegrees[adj_course] -= 1 if indegrees[adj_course] == 0: queue.append(adj_course) return count == numCourses
- Time Complexity: ~V + E
- Space Complexity: ~V + E
where V is the number of courses, and E is the number of dependencies.