fork download
  1. def topsort():
  2.  
  3. def dfs(node):
  4.  
  5. explored[ node ] = True
  6.  
  7. for k in range( 1, nodes + 1):
  8.  
  9. if explored[ k ] is False and matrix[ node ][ k ] == 1:
  10.  
  11. dfs( k )
  12.  
  13. sol.append(node)
  14.  
  15. def reverse2(list):
  16.  
  17. i = 0
  18.  
  19. j = len(list)-1
  20.  
  21. while i < j:
  22.  
  23. list[i],list[j] = list[j], list[i]
  24.  
  25. i +=1
  26.  
  27. j -=1
  28.  
  29. def reverse(list):
  30. newList = list[::-1]
  31. return newList
  32.  
  33.  
  34. #file = open("topsort.in", "r")
  35.  
  36. #grab the number of the nodes and edges
  37. list = [int(i) for i in input().split(" ")]
  38. nodes = list[0];
  39. edges = list[1];
  40.  
  41. #define the matrix
  42. matrix = [[0 for column in range(nodes+1)] for row in range(nodes+1)]
  43. explored = [False] * (nodes+1)
  44. sol = []
  45. for i in range(0, edges):
  46. line = input().split(" ")
  47. x = int(line[0])
  48. y = int(line[1])
  49. matrix[x][y] = 1
  50. edges-=1
  51.  
  52. for i in range(1, nodes+1):
  53.  
  54. if(explored[i] is False):
  55.  
  56. dfs( i )
  57.  
  58. sol = reverse( sol )
  59.  
  60. print( sol )
  61.  
  62. topsort()
Success #stdin #stdout 0.03s 9780KB
stdin
9 8
1 2
1 3
3 4
3 5
5 9
4 6
4 7
4 8
stdout
[1, 3, 5, 9, 4, 8, 7, 6, 2]