Advertisement
Guest User

Untitled

a guest
May 26th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.80 KB | None | 0 0
  1. def topsort():
  2.     cycle = False
  3.     for i in range(n):
  4.         cycle = dfs(i)
  5.         if cycle:
  6.             return false
  7.    
  8.     for i in range(n):
  9.         numbers[stack.pop()] = i
  10.     return True
  11.  
  12. def dfs (v):
  13.     if color[v] == 1:
  14.         return True
  15.     if color[v] == 2:
  16.         return False
  17.     color[v] = 1;
  18.     for i in range(len(edges[v])):
  19.         if dfs(edges[v][i]):
  20.             return True
  21.  
  22.     stack.append(v)
  23.     color[v] = 2
  24.     return False
  25.  
  26.  
  27. n = int(input()) # число вершин
  28. edges = [list() for i in range(n)]
  29. m = int(input()) # число рёбер
  30. for i in range(m):
  31.     a, b = list(map(int, input().split()))
  32.     edges[a - 1].append(b - 1)
  33.  
  34. stack = list()
  35. numbers = [-1 for i in range(n)]
  36. color = [0 for i in range(n)]
  37.  
  38. topsort()
  39.  
  40. print(numbers)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement