AcWing 848. 有向图的拓扑序列 PYTHON 版本
原题链接
简单
作者:
Gyp
,
2020-03-12 22:42:27
,
所有人可见
,
阅读 662
import collections
n, m = map(int, input().split())
e = collections.defaultdict(set)
di = [0 for i in range(n+1)]
di[0] = -1
for i in range(m):
a, b = map(int, input().split())
if b not in e[a]: ## 建边链表
e[a].add(b)
di[b] += 1
q, res = [], [] ## 把入度为0的入队
for i in range(n+1):
if di[i] == 0:
q.append(i)
while len(q) != 0:
cur = q.pop()
res.append(cur)
for v in e[cur]: ## 更新入度,并把入度为0的放入队列
di[v] -= 1
if di[v] == 0:
q.append(v)
if len(res) == n:
print(" ".join(map(str, res)))
else:
print(-1)