⚠️ 第二遍忘了换反图会怎样

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

还是那七个点，这次把 5 → 3 那条边加回来，于是图里有了环：补上选图那一行：second_reversed 为真走反图，为假就是写错的那一版（第二遍还走原图）。两版各跑一次，输出各自的分量个数。

提交你的答案

请登录后提交答案。

去登录

← 自己写：第二遍在反图上收点自己写：列出互相都走得到的点对 →

更多题目

代码编辑器

语言： 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 order_by_finish(g):
    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()
    return order

def kosaraju(edges, second_reversed):
    g = build(edges)
    rg = build([(b, a) for a, b in edges])
    order = order_by_finish(g)
    # TODO: second_reversed 为真时第二遍走反图 rg，为假时（写错的那版）走原图 g
    second = None
    seen, groups = set(), []
    for s in reversed(order):
        if s in seen:
            continue
        st, grp = [s], []
        seen.add(s)
        while st:
            u = st.pop()
            grp.append(u)
            for v in second[u]:
                if v not in seen:
                    seen.add(v)
                    st.append(v)
        groups.append(sorted(grp))
    return sorted(groups)

print(str(len(kosaraju(G, True))) + "/" + str(len(kosaraju(G, False))))

本次输入：

输出：

👩‍🏫

💬 题目评论

⚠️ 第二遍忘了换反图会怎样

更多题目

全部评论