Advertisement
viligen

story_teller_topological_sorting_dfs

Aug 11th, 2022
660
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.87 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. def top_sort_dfs(node, sorted_nodes, graph, visited, cycles):
  5.     if node in cycles:
  6.         raise Exception
  7.     if node in visited:
  8.         return
  9.     visited.add(node)
  10.     cycles.add(node)
  11.  
  12.     for child in graph[node]:
  13.         top_sort_dfs(child, sorted_nodes, graph, visited, cycles)
  14.     sorted_nodes.appendleft(node)
  15.     cycles.remove(node)
  16.  
  17.  
  18. graph = {}
  19. visited = set()
  20. cycles = set()
  21. sorted_nodes = deque()
  22.  
  23. while True:
  24.     line = input().split('->')
  25.     if 'End' == line[0]:
  26.         break
  27.     if len(line) == 1 or line[1].strip() == '':
  28.         graph[line[0].strip()] = []
  29.     else:
  30.         graph[line[0].strip()] = line[1].strip().split(' ')
  31. try:
  32.     for node in graph:
  33.         top_sort_dfs(node, sorted_nodes, graph, visited, cycles)
  34.     print(*sorted_nodes)
  35. except Exception:
  36.     print('Invalid topological sorting')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement