GRL_4_B: Topological Sort (続き6)
解説を読む
そうか、始点を取り出せるようにするほどのことではなくて
入次数覚えておけばいいだけだったか
単純なことなんだけどいったんこれでいける、うまくいった、と思うと
なかなか頭が切り替わらないんだなあ
passedがなくせないかと思ったけど解答サンプルも似たようなことをやってた
そういえばWHITE・GRAY・BLACKはやめたんだな
ついでに深さ優先の方もやってみた
sortの中身が変わるだけ(というかほぼvisitの中身が変わるだけ)
def sort(V):
W = []
def visit(v):
v.passed = True
W.append(v)
for a in v.adj:
a.indeg -= 1
if a.is_start():
visit(a)
for v in V:
if v.is_start() and not v.passed:
visit(v)
return W
深さ優先のほうが単純な再帰で書けて好きだなあ
速さはほとんど同じ