# solution 1 - DFS + hashmap - myself
	# time: O(course + prerequisites) # because every course will be accessed up to two times and every dependency edge will be accessed once
	def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
		# {1: [0]} means that course 1 depends on course 0 (i.e. do course 0 first, and then course 1)
		prerequisitesMap = {}
		for course, prerequisite in prerequisites:
			if course not in prerequisitesMap:
				prerequisitesMap[course] = []
			prerequisitesMap[course].append(prerequisite)
	
		# to store all visited courses along the cur DFS path to detect a circle
		pathNodes = set()
		def dfs(course):
			if course in pathNodes:  # means this course has been visited (i.e., we detect a loop), and thus cannot finish all courses
				return False
			if not prerequisitesMap.get(course, []):  # means this course doesn't have prerequisites
				return True
	
			pathNodes.add(course)
			for prerequisite in prerequisitesMap[course]:
				if not dfs(prerequisite):
					return False
			pathNodes.remove(course)  # we need this, an edge case: [[3,1],[1,4],[3,2],[2,4]] got a wrong result
			prerequisitesMap[
				course] = []  # call this function to reduce unnecessary recursion, e.g., [[0,1],[1,3],[3,4],[4,5],[0.4]]
			return True
	
		for course in range(numCourses):
			if not dfs(course):
				return False
		return True

 # BFS TODO	

	# solution 1 - DFS + hashmap - myself
	# time: O(course + prerequisites) # because every course will be accessed up to two times and every dependency edge will be accessed once
	def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
		prerequisitesMap = {}
		for course, prerequisite in prerequisites:
			if course not in prerequisitesMap:
				prerequisitesMap[course] = []
			prerequisitesMap[course].append(prerequisite)

		# to store all visited courses along the cur DFS path to detect a circle
		pathNodes = set()
		# to avoid an element to be added to res multiple times
		resSet = set()
		res = []

		def dfs(course):
			if course in pathNodes:  # means this course has been visited (i.e., we detect a loop), and thus cannot finish all courses
				return False
			if course in resSet:
				return True

			pathNodes.add(course)
			for prerequisite in prerequisitesMap.get(course, []):
				if not dfs(prerequisite):
					return False

			res.append(course)  # we need this, an edge case: [[3,1],[1,4],[3,2],[2,4]] got a wrong result
			resSet.add(course)
			pathNodes.remove(course)
			return True

		for course in range(numCourses):
			if not dfs(course):
				return []

		return res