ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト G - Longest Path

問題
提出コード
あきらかにこれで使えそうな問題ですね…

解法

グラフにおいて、スタート地点(入次数が0である頂点)に近い方から順番に、その頂点がゴールだったと仮定した場合における最長の距離を確定させていきます。
幅優先探索のようなものをします。
まず、queueに、入次数が0である頂点を格納します。これらの頂点は、最長距離が0となります。
以降はqueueの先頭を取り出し、次のような操作を繰り返します:

  • 取り出した頂点から出ている辺をすべて確認し、その辺を除去する
    それぞれの有向辺について、行き先の頂点の出次数が1つ減ります。

  • 出次数が0となった頂点の処理を行う
    具体的には、今見ている頂点の最長距離+1を、新たに出次数が0となった頂点の距離にし、そしてその頂点をqueueに格納します。

これを繰り返せば、全ての頂点について、その頂点をゴールと仮定したときの最長距離が求められるので、あとはその最大値を出力してあげれば答えになります。