kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

GRL_4_B: Topological Sort (続き)

あんまりかっこいい解き方は思いつかないので
まずは探索で大小を求めてソートする、っていう考え方があっているかどうか
やってみよう
PoCってやつだな!違うかな
TLEなら成功

探索は、閉路がないことを前提にしているので単純
なんとなく幅優先のほうがそれっぽいので幅優先で

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

    def __lt__(self, other):
        S = []
        S.append(self)

        while S:
            v = S.pop()
            for a in v.adj:
                if other == a:
                    return True
                else:
                    S.append(a)
        return 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 main():
    nv, ne = [int(x) for x in input().split()]
    V = [Node(id) for id in range(nv)]
    read_edges(ne, V)
    V.sort()
    [print(v.id) for v in V]

if __name__ == '__main__':
    main()

Case #14でWA
えーWAですか
PoC失敗なの?

caseNameが03_rand_01.in
smallとかcornerって名前がついたケースはACで
ランダムで間違えるって何かなあ
細かく見るのは明日にする