Advertisement
PlotnikovPhilipp

Untitled

Nov 17th, 2019
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.07 KB | None | 0 0
  1. def topologicSort(graph): # граф ориентированный, в виде словаря, нападобии списка смежности
  2.     resultArr = []
  3.     visited = []
  4.     while len(graph) != len(visited):
  5.         for s1 in graph.keys():
  6.             s1 = int(s1)
  7.             for s2 in graph.values():
  8.                 if s1 in s2 or s1 in visited:
  9.                     break
  10.             else:
  11.                 resultArr.append(s1)
  12.                 visited.append(s1)
  13.                 if len(visited) == len(graph):
  14.                     resultArr.extend(graph[s1])
  15.                 graph[s1] = [s1]
  16.                 break
  17.     return resultArr
  18. n, m = [int(i) for i in input().split()] # n - кол-во вершин, m - кол-во ребер
  19. test_graph = {}
  20. for i in range(m):
  21.     first, last = [int(i) for i in input().split()]
  22.     if first not in test_graph:
  23.         test_graph[first] = []
  24.     test_graph[first].append(last)
  25. arr = sorted(test_graph)
  26. arr.reverse()
  27. graph = {}
  28. for i in arr:
  29.     graph[i] = test_graph[i]
  30. print(graph)
  31. print(topologicSort(graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement