The implementation is a bit different as it does not strictly follow the Kahn's algorithm maintaining a set of vertices with no incoming edges.
The implementation does not fit in my brain right now, but it is worth remembering the existence of this variation.
def topological_sort_util(
v: int,
adj: list[list[int]],
visited: list[bool],
stack: list,
):
visited[v] = True
for i in adj[v]:
if not visited[i]:
topological_sort_util(i, adj, visited, stack)
stack.append(v)
def topological_sort(adj: list[list[int]], V: int):
# stack to store the result
stack = []
visited = [False] * V
for i in range(V):
if not visited[i]:
topological_sort_util(i, adj, visited, stack)
result = []
while stack:
result.append(stack.pop())
return result
if __name__ == "__main__":
V = 4
edges = [[0, 1], [1, 2], [3, 1], [3, 2]]
adj = [[] for _ in range(V)]
for s, t in edges:
adj[s].append(t)
result = topological_sort(adj, V)
print(result) # [3, 0, 1, 2]from collections import defaultdict
def topological_sort(V, edges_map, incoming) -> list[int]:
result = []
stack = []
for v in range(V):
if incoming[v] == 0:
stack.append(v)
while stack:
v_to_remove = stack.pop()
for target_v in edges_map[v_to_remove]:
incoming[target_v] -= 1
if incoming[target_v] == 0:
stack.append(target_v)
result.append(v_to_remove)
return result
if __name__ == "__main__":
V = 4
edges = [(0, 1), (1, 2), (3, 1), (3, 2)]
incoming = [0] * V
for s, t in edges:
incoming[t] += 1
edges_map = defaultdict(list)
for s, t in edges:
edges_map[s].append(t)
result = topological_sort(V, edges_map, incoming)
print(result) # [3, 0, 1, 2]A doubt on its time complexity arises, but I lack the ability to consider the problem right now. I'll come back later.
Rice Roni 400 Sandwitch 500 Rice 400 Mashed potatoes 500
Total 1800 kcal
push-ups
MUST:
uvTODO: