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