自己写：缩点后最长的一条链

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

把上一节那张有环的图缩点：每个强连通分量捏成一个点，分量之间的边保留（去掉重边和自环）。缩完是一张 DAG，可以放心求最长链了。补全 longest，输出最长的一条链经过几个分量。

提交你的答案

请登录后提交答案。

去登录

← 自己写：把缩点后的图建出来自己写：从哪几个点出发能走遍全图 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

def build(edges):
    g = {u: [] for u in range(N)}
    for a, b in edges:
        g[a].append(b)
    for u in g:
        g[u].sort()
    return g

def kosaraju(edges, second_reversed=True):
    g = build(edges)
    rg = build([(b, a) for a, b in edges])
    seen, order = set(), []
    for s in range(N):
        if s in seen:
            continue
        st = [(s, iter(g[s]))]
        seen.add(s)
        while st:
            u, it = st[-1]
            for v in it:
                if v not in seen:
                    seen.add(v)
                    st.append((v, iter(g[v])))
                    break
            else:
                order.append(u)
                st.pop()
    second = rg if second_reversed else g
    seen2, groups = set(), []
    for s in reversed(order):
        if s in seen2:
            continue
        st, grp = [s], []
        seen2.add(s)
        while st:
            u = st.pop()
            grp.append(u)
            for v in second[u]:
                if v not in seen2:
                    seen2.add(v)
                    st.append(v)
        groups.append(sorted(grp))
    return sorted(groups)

gs = kosaraju(G)
comp = {}
for i, grp in enumerate(gs):
    for u in grp:
        comp[u] = i
ce = sorted({(comp[a], comp[b]) for a, b in G if comp[a] != comp[b]})
M = len(gs)

def longest(nodes, edges):
    g = {u: [] for u in nodes}
    d = {u: 0 for u in nodes}
    for a, b in edges:
        g[a].append(b)
        d[b] += 1
    ready = [u for u in nodes if d[u] == 0]
    dp = {u: 1 for u in nodes}
    while ready:
        u = ready.pop(0)
        # TODO: u 的每个后继 v，dp[v] 取 max(dp[v], dp[u] + 1)
        # TODO: 再把 d[v] 减 1，减到 0 就排进 ready
    return max(dp.values())

print(longest(list(range(M)), ce))

本次输入：

输出：

👩‍🏫

💬 题目评论

自己写：缩点后最长的一条链

更多题目

全部评论