Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import defaultdict
- class Graph:
- def __init__(self,vertices):
- self.graph = defaultdict(list)
- self.V = vertices
- def addEdge(self,u,v):
- self.graph[u].append(v)
- def topologicalSort(self):
- in_degree = [0]*(self.V)
- for i in self.graph:
- for j in self.graph[i]:
- in_degree[j] += 1
- queue = []
- for i in range(self.V):
- if in_degree[i] == 0:
- queue.append(i)
- cnt = 0
- top_order = []
- while queue:
- u = queue.pop(0)
- top_order.append(u)
- for i in self.graph[u]:
- in_degree[i] -= 1
- if in_degree[i] == 0:
- queue.append(i)
- cnt += 1
- if cnt != self.V:
- print ("Impossible")
- else :
- print (top_order)
- n,m = input().split(" ")
- n = int(n)
- m = int(m)
- g = Graph(n)
- for i in range (m):
- u,v = input().split(" ")
- u = int(u)
- v = int(v)
- g.addEdge(u, v);
- m -= 1
- g.topologicalSort()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement