競技プログラミング総合スレ 66

200 ：デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb)：2023/04/10(月) 22:32:19.30 ID:GqegRxcS0.net

この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。

トポロジカルソートを使ってそのコードを書き換えるとこうなります。
https://ideone.com/1NbHIf