Given each course prerequesites (prerequesites are other course), check if it is possible to finish every courses.
The goal of the algorithm is to check if there is no loop in the prerequesites. It is done using dfs from a node. When entering a dfs from a given node, we set it to a given value that means that if we encounter again this node in the dfs hence there is a loop. At the end of the dfs for this node, we set it to another value that means 'this node is safe'. We then check for every course if we can finish it.
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Create graph
graph = defaultdict(set)
for i, j in prerequisites:
graph[i].add(j)
visit = [0 for _ in range(numCourses)] # 0 means that course i has not been checked (1 means course is safe and -1 means course contains loop)
def dfs(i):
if visit[i] != 0:
return(visit[i] == 1)
# start checking prerequisites of course i; , set to -1 which means "curently looking loop from this course"; if found again during pass it means that a loop exists
visit[i] = -1
# check prerequisites of all prerequisites of course i
for j in graph[i]:
if not dfs(j):
return False
visit[i] = 1 # checking of element i done, set to 1 which means "no loop from this course"
return True
# Check all courses as 'final course'
for i in range(numCourses):
if not dfs(i):
return False
return True