串行要七轮,并行要几轮

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

还是那七个构建任务。这次机器不限:一轮里所有"依赖都做完了"的任务可以同时开工。下面这段把任务分成一层一层,每一层里的任务可以同时开工。输出串行轮数并行轮数

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

def layers(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
    cur = sorted(u for u in range(N) if d[u] == 0)
    out = []
    while cur:
        out.append(cur)
        nxt = []
        for u in cur:
            for v in g[u]:
                d[v] -= 1
                if d[v] == 0:
                    nxt.append(v)
        cur = sorted(nxt)
    return out

L = layers(DEP)
print(str(N) + "/" + str(len(L)))
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论