Advertisement
smj007

Untitled

Feb 12th, 2024
1,173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.99 KB | None | 0 0
  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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement