# Untitled

Feb 12th, 2024
1,173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution:
2.     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3.
4.         # DP with memoization
5.         # state: 0 - unvisited
6.         # state: 1 - visited but not finished
7.         # state: 2 - visited and finished
8.         visit = [0]*numCourses
9.         from collections import defaultdict
10.         mapping = defaultdict(list)
11.         for (crs, prereq) in prerequisites:
12.             mapping[crs].append(prereq)
13.
14.         def dfs(course):
15.             if visit[course] == 1:
16.                 return False
17.
18.             if visit[course] == 2:
19.                 return True
20.
21.             visit[course] = 1
22.
23.             for neighbour in mapping[course]:
24.                 run = dfs(neighbour)
25.                 if run is False:
26.                     return False
27.
28.             visit[course] = 2
29.             return True
30.
31.         for crs in range(numCourses):
32.             run = dfs(crs)
33.             if run is False:
34.                 return False
35.
36.         return True