辺の深さ優先探索
https://gyazo.com/1957f5e7122ed77931ef8d0dbf313033
ARC111D
無向グラフが与えられて、強連結成分になるように辺に向き付けをしたい
1は頂点の深さ優先探索、これだと通らない辺がある
3が正しい辺の深さ優先探索
2はうっかり間違えたもの
将来訪問する辺をスタックに積むタイミングで塗ってしまった
Cの頂点から出る辺がなくなっている
3
code: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 edgesv2:
if v3 == v1:
continue
if (v2, v3) in answer:
continue
answer(v2, v3) = "->"
answer(v3, v2) = "<-"
visit((v2, v3))
visit((v1, v2))
2
code: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 edgesv2:
if v3 == v1:
continue
if (v2, v3) in answer:
continue
answer(v2, v3) = "->"
answer(v3, v2) = "<-"
stack.append((v2, v3))
2を再帰呼び出しなしで実装したもの
塗るタイミングを実際に辺をたどったタイミングにする
既に塗った辺がスタックに入ってることがあるので、塗られてないことをチェックしてから塗る
code: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 edgesv2:
if v3 == v1:
continue
stack.append((v2, v3))
深さ優先探索