def print_orders(tasks, prerequisites):
degreemap, adjlist = {}, {}
for t in range(tasks):
degreemap[t] = 0
adjlist[t] = []
for (v1, v2) in prerequisites:
adjlist[v1].append(v2)
degreemap[v2] += 1
all_schedules = []
def dfs(path):
if len(path) == tasks:
all_schedules.append(path.copy())
next_sources = (
t for t in range(tasks) if degreemap[t] == 0
) # determine active sources (i.e degree = 0)
for s in next_sources:
degreemap[s] -= 1 # prevents double selection
path.append(s)
for child in adjlist[s]:
degreemap[child] -= 1 # updates child degree
dfs(path)
# backtracking
path.pop()
for child in adjlist[s]:
degreemap[child] += 1
degreemap[s] += 1
dfs([])
for schedule in all_schedules:
print(schedule)
return all_schedules
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/4994209155121152