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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
from collections import defaultdict, deque
# 1) the forward edge graph
forward = {
2: [3, 8],
3: [4],
4: [5, 8, 14],
5: [6],
6: [14],
7: [],
8: [9],
9: [10],
10: [12],
11: [14],
12: [11],
13: [],
14: []
}
# prereqs[v] = list of u
prereqs = defaultdict(list)
for u, vs in forward.items():
for v in vs:
prereqs[v].append(u)
# 2) Part 1: perform BFS with flipped graph from 14 to collect ancestors
rev = defaultdict(list)
for u, vs in forward.items():
for v in vs:
rev[v].append(u)
ancestors = set()
q = deque([14])
while q:
v = q.popleft()
if v in ancestors:
continue
ancestors.add(v)
for u in rev[v]:
q.append(u)
# 3) Part 2: loop to get prereqs from ancestors
schedule = []
covered = set()
remaining = set(ancestors)
while remaining:
# find any chapter in remaining whose prereqs are all in covered
for v in sorted(remaining):
if all(p in covered for p in prereqs[v]):
schedule.append(v)
covered.add(v)
remaining.remove(v)
break
# 4) print with names
titles = {
2: "Fundamental Algorithms",
3: "The Euclidean Algorithm",
4: "Applications of Euclid's Algorithm",
5: "Modular Algorithms",
6: "Resultants and GCD Computation",
8: "Fast Multiplication",
9: "Newton Iteration",
10: "Fast Evaluation and Interpolation",
11: "Fast Euclidean Algorithm",
12: "Fast Linear Algebra",
14: "Factoring over Finite Fields",
}
print("Your course sequence is:")
for ch in schedule:
print(f" Chapter {ch}: {titles[ch]}")
|
