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

from typing import List from collections import defaultdict
def topological_sort(vertices: int, edges: List[List[int]]) > List[int]: ''' Args: vertices: 0, 1, 2, .... , vertices1 edges: (start, end, weight) Return: A valid topological ordering Raise: ValueError: if there is not a valid topological ordering. ''' graph, indegrees = defaultdict(set), [0] * vertices for (start, end, weight) in edges: graph[start].add(end) indegrees[end] += 1 zero_degrees = [vertex for vertex, indegree in enumerate(indegrees) if indegree == 0] ordering = [] while zero_degrees: vertex = zero_degrees.pop() ordering.append(vertex) for successor in graph[vertex]: indegrees[successor] = 1 if indegrees[successor] == 0: zero_degrees.append(successor) if len(ordering) != vertices: raise ValueError('There is not a valid topological ordering') return ordering
ordering = topological_sort(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]]) print('>'.join([str(vertex) for vertex in ordering]))
