⚠️ 多一条依赖,就排不全了

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

箭头一改,就开不了工

排得开

排不开

七个构建任务编号 0~6(a, b) 表示 a 做完才能做 b:再给它加上一条 5 → 3,然后两张图各排一次,各输出排出来的个数:

DEP = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)]
BACK = (5, 3)
N = 7

def kahn(edges):
    g = {u: [] for u in range(N)}
    d = {u: 0 for u in range(N)}
    for a, b in edges:
        g[a].append(b)
        d[b] += 1
    ready = sorted(u for u in range(N) if d[u] == 0)
    out = []
    while ready:
        u = ready.pop(0)
        out.append(u)
        for v in g[u]:
            d[v] -= 1
            if d[v] == 0:
                ready.append(v)
        ready.sort()
    return len(out)

print(str(kahn(DEP)) + "/" + str(kahn(DEP + [BACK])))
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论