拼多多-笔试题(拓补排序)

m, n = input().split()
cost = input().split()
m, n = int(m), int(n)
cost =[int(each) for each in cost]
degree = {}
depend = {}
for i in range(len(cost)):
    degree[i+1] = 0

while n:
    n-=1
    ref = input().split()
    if int(ref[0]) not in depend:
        depend[int(ref[0])]=[]
    depend[int(ref[0])].append(int(ref[1]))
    degree[int(ref[1])]+=1
que = []
for i in range(1, m+1):
    if degree[i]==0:
        que.append([i, cost[i-1]])
        degree[i] = -1
ans = []
while len(que)>0:
    que.sort(key=lambda x:(x[1], x[0]))
    node = que.pop(0)
    ans.append(node[0])
    if node[0] not in depend:
        continue 
    for each in depend[node[0]]:
        degree[each]-=1
    for i in range(1, m+1):
        if degree[i]==0:
            que.append([i, cost[i-1]])
            degree[i]=-1
    
print(' '.join([str(each) for each in ans]))

 

上一篇:hdu 2454 Degree Sequence of Graph G(可简单图化判定)


下一篇:python selenium 相关操作