Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. from collections import defaultdict
  2.  
  3. class Graph:
  4. def __init__(self,vertices):
  5. self.graph = defaultdict(list)
  6. self.V = vertices
  7.  
  8. def addEdge(self,u,v):
  9. self.graph[u].append(v)
  10.  
  11. def topologicalSort(self):
  12.  
  13. in_degree = [0]*(self.V)
  14.  
  15. for i in self.graph:
  16. for j in self.graph[i]:
  17. in_degree[j] += 1
  18.  
  19. queue = []
  20. for i in range(self.V):
  21. if in_degree[i] == 0:
  22. queue.append(i)
  23.  
  24. cnt = 0
  25.  
  26. top_order = []
  27.  
  28. while queue:
  29.  
  30. u = queue.pop(0)
  31. top_order.append(u)
  32.  
  33. for i in self.graph[u]:
  34. in_degree[i] -= 1
  35.  
  36. if in_degree[i] == 0:
  37. queue.append(i)
  38.  
  39. cnt += 1
  40.  
  41. if cnt != self.V:
  42. print ("Impossible")
  43. else :
  44. print (top_order)
  45.  
  46. n,m = input().split(" ")
  47. n = int(n)
  48. m = int(m)
  49. g = Graph(n)
  50.  
  51. for i in range (m):
  52. u,v = input().split(" ")
  53. u = int(u)
  54. v = int(v)
  55. g.addEdge(u, v);
  56. m -= 1
  57.  
  58. g.topologicalSort()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement