⚠️ 多一条依赖,就排不全了
箭头一改,就开不了工
排得开
排不开
七个构建任务编号 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])))
全部评论