I completely forgot about the algorithm, so this is just my attempt to make it work.
Topological sorting - Wikipedia
Kahn’s algorithm
One of these algorithms, first described by Kahn (1962), works by choosing vertices in the same order as the eventual topological sort. First, find a list of “start nodes” that have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty (finite) acyclic graph. Then:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)from collections import deque
n = 6
edges: list[tuple[int, int]] = [
(5, 0),
(5, 2),
(3, 1),
(4, 0),
(4, 1),
(2, 3),
]
result: list[int] = []
incoming: list[int] = [0] * n
for s, t in edges:
incoming[t] += 1
q = deque()
for node_i in range(n):
if incoming[node_i] == 0:
q.append(node_i)
while q:
node_to_remove = q.popleft()
for s, t in edges:
if s == node_to_remove:
incoming[t] -= 1
if incoming[t] == 0:
q.append(t)
result.append(node_to_remove)
print(result)
# [4, 5, 0, 2, 3, 1]I didn't optimize the code, but now I remember the algorithm (to some extent).
We count the number of incoming edges, remove node with no incoming edges from the graph, update the incoming edge counts, and repeat these steps.
20231030: by converting the edge list into a hashmap will decrease the time complexity to (V + E) where V is the number of vertices and E is the number of edges.
Udon 800 Sandwitch 300 m&m's 300 Kombucha 200
Total 1600 kcal
6 mi run, push-ups
MUST:
uvTODO: