GRL_4_B: Topological Sort (続き5)

しばらく間があいてしまいましたがその間にちょっと降りてきた気が

始点を探して幅優先探索して見つかった順に結果に入れていけば
だいたいはうまくいくはず
うまくいかない可能性があるのは複数の枝が合流する地点
合流地点に来たとき、まだほかにそこへ合流してくる枝があれば
その枝の処理はそこで止めて、最後に合流してきた枝で探索を
継続すればうまくいくんじゃないか

なんとなくまだごちゃっとしそうだけど書いてみる

class Node():
    def __init__(self, id):
        self.id = id
        self.adj = []
        self.passed = False

def read_edges(ne, V):
    for _ in range(ne):
        s, t = [int(x) for x in input().split()]
        V[s].adj.append(V[t])

def is_start(V, node):
    for v in V:
        if node in v.adj:
            return False
    return True

def is_last_branch(V, node):
    for v in V:
        if node in v.adj and not v.passed:
            return False
    return True

def sort(V):
    W = []

    def rec(v):
        S = []
        S.append(v)

        while S:
            v = S.pop()
            v.passed = True
            W.append(v)
            for a in v.adj:
                if is_last_branch(V, a):
                    S.append(a)

    for v in V:
        if is_start(V, v):
            rec(v)

    return W

def main():
    nv, ne = [int(x) for x in input().split()]
    V = [Node(id) for id in range(nv)]
    read_edges(ne, V)
    W = sort(V)
    [print(v.id) for v in W]

if __name__ == '__main__':
    main()

Case #24 (5000頂点 17439エッジ)まで進んだ！

始点を探したり合流してくる枝を探したりするところでループを
回してるのが遅そうだ
一発で判定できる工夫はないかな
始点→終点だけ持つんじゃなくて、終点から始点をたどれるようにするといいだろうか

終点から始点をたどる方は、使ったら削除していくようにすれば
始点を探す処理と合流してくる枝を探す処理がひとつにまとまるな
いいぞいいぞ

削除はちょっと時間かかるかもだけど組み込み関数があるし
まずはやってみよう

あれ？
これ幅優先探索してる意味あったっけ？
ただ始点を探し続ければいいだけじゃない？
外側のループだけ回したらよかったりしない？
いや、だめか（自己解決
でも、やってることは始点を求め続けてるってことだな

こうか

class Node():
    def __init__(self, id):
        self.id = id
        self.adj = []
        self.radj = []
        self.passed = False

    def is_start(self):
        return self.radj == []

def read_edges(ne, V):
    for _ in range(ne):
        s, t = [int(x) for x in input().split()]
        V[s].adj.append(V[t])
        V[t].radj.append(V[s])

def sort(V):
    W = []

    def visit(v):
        S = []
        S.append(v)

        while S:
            v = S.pop()
            v.passed = True
            W.append(v)
            for a in v.adj:
                a.radj.remove(v)
                if a.is_start():
                    S.append(a)

    for v in V:
        if v.is_start() and not v.passed:
            visit(v)

    return W

よしAC

ほか何かあるかな
passedは消せないだろうか
始点かどうかの判定に使ってるだけなんだけど
radjを消すようにしたから必要になってしまったんだよな
何か一石二鳥の手はないか

ところでこれ、幅優先じゃなくて深さ優先でも動きますね
試してないけど
合流のところさえやればどっちでも問題ない
アイコンが幅優先・深さ優先両方あったのはそういうことか