题解 | #【模板】拓扑排序#

# 拓扑排序，有向图
# 适用场合：按照箭头指向，先后顺序排列。如修课顺序，修完高等数学才能修离散数学。
# 1. 找到无入度的顶点
# 2. 任选其中一点写入排序队列
    # 6 4
    # 2 3
    # 9 4
    # 4 5
    # 2 8


'输入点的个数，边的个数'
p_n, e_n = map(int,input().split()) 

'输入有向边, 用dict存储'
graph = dict()
for e in range(e_n):
    s,e = input().split()
    if s not in graph:
        graph[s] = []
    graph[s].append(e) # {'2': ['3', '8'], '9': ['4'], '4': ['5']}

'计算所有节点的入度数量'
inDegree = dict() # 入度数量，{'2': 0, '3': 1, '8': 1, '9': 0, '4': 1, '5': 1}
def count_indegree(i,loc='value'):
    if i not in inDegree:
        inDegree[i] = 0 if loc == 'key' else 1
    else:
        inDegree[i] = inDegree[i]+1 if loc == 'value' else inDegree[i]
for i in graph:
    count_indegree(i,loc='key')
    for j in graph[i]:
        count_indegree(j,loc='value') 
    
'寻找入度为0的节点' 
zero_point = [i for i in inDegree if inDegree[i]==0]
res = [] # 排序
while zero_point:
    c = zero_point.pop() # 随机去掉入度为0的点
    res.append(c)
    if c in graph:
        for i in graph[c]: # 对所有该节点指向的所有节点，入度数-1
            inDegree[i] -= 1
            if inDegree[i] == 0:
                zero_point.append(i)

if len(res) == p_n:
    print(' '.join(res))
else:
    print(-1)