Course Schedule

BFSDFSTopological Sort

# Solution

# Kahn's Algorithm (BFS)

Complexity

time: $O(V + E)$
space: $O(V + E)$

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# trivial case
if numCourses == 0:
return False

edges = {i: set() for i in range(numCourses)} # other courses that depend on course i
indegrees = [0 for _ in range(numCourses)] # number of unlearned prereqs

# calc indegrees for each course
for i, j in prerequisites:
# if A -> B, then B's indegrees + 1
indegrees[i] += 1

# add courses w/ 0 indegree to queue
queue = []
for i in range(numCourses):
if indegrees[i] == 0:
queue.append(i)

# finish courses in queue & update indegrees
numFinished = 0
while queue:
now = queue.pop(0)
numFinished += 1
# all courses that have the finished now for prereq decrement indegrees by 1
for i in edges[now]:
indegrees[i] -= 1
# if course i has no prereq, add to queue
if indegrees[i] == 0:
queue.append(i)

# check if numFinished is all the courses; otherwise, the graph is not a DAG
if numFinished != numCourses:
return False
return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36