Advertisement
PlotnikovPhilipp

Untitled

Nov 17th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.92 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.     return resultArr
  17. n, m = [int(i) for i in input().split()] # n - кол-во вершин, m - кол-во ребер
  18. graph = {}
  19. for i in range(m):
  20.     first, last = [int(i) for i in input().split()]
  21.     if first not in graph:
  22.         graph[first] = []
  23.     graph[first].append(last)
  24. print(topologicSort(graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement