# 207 Course Schedule

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`.

• For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return `true` if you can finish all courses. Otherwise, return `false`.

Example 1:

``````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.
``````

Example 2:

``````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.
``````

Constraints:

• `1 <= numCourses <= 2000`
• `0 <= prerequisites.length <= 5000`
• `prerequisites[i].length == 2`
• `0 <= ai, bi < numCourses`
• All the pairs `prerequisites[i]` are unique.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 `````` ``````class Solution: def canFinish( self, numCourses: int, prerequisites: List[List[int]] ) -> bool: child_map = {} for p in prerequisites: child_map.setdefault(p[0], []).append(p[1]) # 0: not_visited, 1: being_visited, 2: visited visited = [0] * numCourses for c in range(numCourses): if not self.is_valid(c, visited, child_map): return False return True def is_valid( self, c: int, visited: List[int], child_map: Dict[int, List[int]] ) -> bool: """ DFS """ if visited[c] == 2 or c not in child_map: return True if visited[c] == 1: return False visited[c] = 1 for child in child_map[c]: if not self.is_valid(child, visited, child_map): return False visited[c] = 2 return True``````