辺の深さ優先探索

ARC111D

• 無向グラフが与えられて、強連結成分になるように辺に向き付けをしたい

• 1は頂点の深さ優先探索、これだと通らない辺がある

• 3が正しい辺の深さ優先探索

• 2はうっかり間違えたもの

  • 将来訪問する辺をスタックに積むタイミングで塗ってしまった
  • Cの頂点から出る辺がなくなっている

• 3 python

for 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 python

for 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を再帰呼び出しなしで実装したもの
  • 塗るタイミングを実際に辺をたどったタイミングにする
  • 既に塗った辺がスタックに入ってることがあるので、塗られてないことをチェックしてから塗る python

for 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))

深さ優先探索