AcWing 848. 有向图的拓扑序列 python
原题链接
简单
作者:
申侠
,
2020-10-31 10:19:47
,
所有人可见
,
阅读 208
class Graph():
def __init__(self,N=100010):
self.h = [-1] * N
self.e = [-1] * N
self.w = [-1] * N
self.ne = [-1] * N
self.idx = 0
self.d = [0] * N
def add(self,a,b):
idx = self.idx
self.e[idx] = b
self.ne[idx] = self.h[a]
self.h[a] = idx
self.d[b] += 1
self.idx += 1
def topology(self,n):
from queue import Queue
q = Queue()
res = []
for i in range(1,n+1):
if self.d[i] == 0:
q.put(i)
while not q.empty():
p = q.get()
res.append(p)
idx = self.h[p]
while idx!= -1:
v = self.e[idx]
self.d[v] -= 1
if not self.d[v]:
q.put(v)
idx = self.ne[idx]
return '-1' if len(res) != n else ' '.join(map(str, res))
n,m = map(int, input().split())
g = Graph()
for _ in range(m):
a,b = map(int, input().split())
g.add(a,b)
res = g.topology(n)
print(res)