Course Schedule

1def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
2    graph = [[] for _ in range(numCourses)]
3    for a, b in prerequisites:
4        graph[a].append(b)
5        
6    visiting = set()
7    visited = set()
8    
9    def dfs(c: int) -> bool:
10        if c in visiting:
11            return False
12        if c in visited:
13            return True
14        visiting.add(c)
15        for pre in graph[c]:
16            if not dfs(pre):
17                return False
18        visiting.remove(c)
19        visited.add(c)
20        return True
21    
22    for c in range(numCourses):
23        if not dfs(c):
24            return False
25    return True