3129: 信息学奥赛一本通T1352-奖金(拓扑排序)

解题思路:

注意事项:

参考代码:

n,m = map(int,input().split())
# 构造图
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = map(int,input().split())
    graph[b].append(a)
# 记录入度
in_degree = {i:0 for i in range(1,n+1)}
for i in graph:
    for j in graph[i]:
        in_degree[j] += 1
# 入度为0的点入列
lst = [i for i in in_degree if in_degree[i] == 0]
# 记录奖金的列表
bonus = [100 for i in range(n)]
# 在开头插入一个0使索引对应
bonus.insert(0,0)

res = []
# 逐个从列表中取出元素
while lst:
    c = lst.pop()
    res.append(c)
    # 取出的元素连接的点入度减小1，如果入度为0则添加到列表中
    for i in graph[c]:
        # 更新奖金：i员工的奖金要比c大
        bonus[i] = max(bonus[i],bonus[c]+1)
        in_degree[i] -= 1
        if in_degree[i] == 0:
            lst.append(i)
# print(bonus)
if len(res) != n:
    print("Poor Xed")
else:
    print(sum(bonus))