202402101032
tags: #graph

class Solution:
	def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
		graph = {}
		visiting = set()
		visited = set()
		res = []
		def dfs(course):
			if course in visited:
				return True
			if course in visiting:
				return False
			visiting.add(course)
			if course in graph:
				for children in graph[course]:
					if not dfs(children):
						return False
			visiting.remove(course)
			visited.add(course)
			return True
		for prerequisite in prerequisites:
			end = prerequisite[1]
			start = prerequisite[0]
		if start in graph:
			graph[start].append(end)
		else:
			graph[start] = [end]
		for children in graph:
			if not dfs(children):
				return False
		return True

Reference

https://leetcode.com/problems/course-schedule/