38 lines
954 B
Python
38 lines
954 B
Python
|
from collections import defaultdict
|
||
|
|
|
||
|
|
class Solution:
|
||
|
|
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
|
||
|
|
graph = defaultdict(list)
|
||
|
|
|
||
|
|
for course, pre in prerequisites:
|
||
|
|
graph[course].append(pre)
|
||
|
|
|
||
|
|
cycles = set()
|
||
|
|
visited = set()
|
||
|
|
|
||
|
|
def dfs(course):
|
||
|
|
if course in cycles:
|
||
|
|
return False
|
||
|
|
|
||
|
|
if course in visited:
|
||
|
|
return True
|
||
|
|
|
||
|
|
visited.add(course)
|
||
|
|
cycles.add(course)
|
||
|
|
|
||
|
|
for dep in graph[course]:
|
||
|
|
if not dfs(dep):
|
||
|
|
return False
|
||
|
|
|
||
|
|
cycles.remove(course)
|
||
|
|
|
||
|
|
return True
|
||
|
|
|
||
|
|
for course in range(numCourses):
|
||
|
|
cycles = set()
|
||
|
|
|
||
|
|
if not dfs(course):
|
||
|
|
return False
|
||
|
|
|
||
|
|
return True
|
||
|
|
|