辺の深さ優先探索

NISHIO Hirokazu [Translate]

辺の深さ優先探索

ARC111D
無向グラフが与えられて、強連結成分になるように辺に向き付けをしたい
1は頂点の深さ優先探索、これだと通らない辺がある
3が正しい辺の深さ優先探索
2はうっかり間違えたもの
将来訪問する辺をスタックに積むタイミングで塗ってしまった
Cの頂点から出る辺がなくなっている

3
pythonfor v1, v2 in edgelist:
    if (v1, v2) not in answer:
        answer[(v1, v2)] = "->"
        answer[(v2, v1)] = "<-"

        def visit(e):
            (v1, v2) = e
            for v3 in edges[v2]:
                if v3 == v1:
                    continue
                if (v2, v3) in answer:
                    continue
                answer[(v2, v3)] = "->"
                answer[(v3, v2)] = "<-"
                visit((v2, v3))
        visit((v1, v2))
2
pythonfor v1, v2 in edgelist:
    if (v1, v2) not in answer:
        answer[(v1, v2)] = "->"
        answer[(v2, v1)] = "<-"
        stack = [(v1, v2)]
        while stack:
            v1, v2 = stack.pop()
            for v3 in edges[v2]:
                if v3 == v1:
                    continue
                if (v2, v3) in answer:
                    continue
                answer[(v2, v3)] = "->"
                answer[(v3, v2)] = "<-"
                stack.append((v2, v3))
2を再帰呼び出しなしで実装したもの
塗るタイミングを実際に辺をたどったタイミングにする
既に塗った辺がスタックに入ってることがあるので、塗られてないことをチェックしてから塗る
pythonfor v1, v2 in edgelist:
    if (v1, v2) not in answer:
        stack = [(v1, v2)]
        while stack:
            v1, v2 = stack.pop()
            if (v1, v2) in answer:
                continue
            answer[(v1, v2)] = "->"
            answer[(v2, v1)] = "<-"
            for v3 in edges[v2]:
                if v3 == v1:
                    continue
                stack.append((v2, v3))

深さ優先探索

"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]

(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:21:37 PM[Edit]

Related Pages