-
無向グラフが与えられて、強連結成分になるように辺に向き付けをしたい
-
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))