Advertisement
Guest User

Untitled

a guest
May 26th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. 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. 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].append(b)
  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