arundeepak

topological sort

Mar 20th, 2016
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.59 KB | None | 0 0
  1. '__author__'=='deepak Singh Mehta(learning to code)) '
  2.  
  3.  
  4. stack,graph,vis,n = [],{},[],int()
  5.  
  6.  
  7. def dfs(v):
  8.   global vis,graph,stack,n
  9.   vis[v]=True
  10.   for i in graph[v]:
  11.     if not vis[i]:
  12.       dfs(i)
  13.   stack.append(v)
  14.  
  15.  
  16. def topSort():
  17.   global vis,graph,stack,n
  18.   vis = [False]*n
  19.   for i in range(n):
  20.     if not vis[i]:
  21.       dfs(i)
  22.   for i in stack[::-1]:
  23.     print(i,end=' ')
  24.    
  25.  
  26. if __name__=='__main__':
  27.   n,m = map(int,input().split())
  28.   for i in range(n):
  29.     graph[i]=[]
  30.   for _ in range(m):
  31.     a,b = map(int,input().split())
  32.     graph[a].append(b)
  33.   topSort()
Add Comment
Please, Sign In to add comment