AcWing 848. 有向图的拓扑序列-python
原题链接
简单
作者:
四舍五入
,
2022-02-22 12:49:56
,
所有人可见
,
阅读 123
python 代码
from collections import deque
N = 100010
def add(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def topsort():
for i in range(1, n + 1):
if not d[i]:
q.append(i)
while q:
t = q.popleft()
ans.append(t)
i = h[t]
while i != -1:
j = e[i]
d[j] -= 1
if d[j] == 0:
q.append(j)
i = ne[i]
return len(ans) == n
if __name__ == '__main__':
h, e, ne, idx = [-1]*N, [0]*N, [0]*N, 0
d = [0]*N
q = deque()
ans = []
n, m = map(int, input().split())
for i in range(m):
a,b = map(int, input().split())
add(a,b)
d[b] += 1
if topsort():
print(" ".join(map(str, ans)))
else:
print('-1')