EDPC G - Longest Path

考え方

ABCでいうと、E問題級。

木の高さを求める深さ優先探索と同じ発想でやればよい。

つまり、トポロジカルソートをして、後ろから順に

• 出次数が $0$ なら高さ $0$
• 出次数が $1$ 以上なら、その行先の高さの最大値 $+1$

を順に計算すればよい。
（この問題だけなら正順で配る DP した方が楽かもしれない）

あとは、全頂点の高さの最大値を出すだけ。
動的計画法本体よりも、トポロジカルソートをすることの方が大変かもしれない。

計算量は、トポロジカルソートの実装にもよるが、一般的な方法なら $O(N+M)$。

入力例1での動作

入力を受け取る。
頂点番号を $1$ 引いて 0-indexed にし、隣接リストを作る。

n: 4
m: 5
graph:
  0: {1, 2}
  1: {3}
  2: {1, 3}
  3: {}

トポロジカルソートすると、例えば次の順序になる。

{0, 2, 1, 3}

各頂点から始めて、最大で何本の辺を辿れるかを考える。

頂点 $3$ から出る辺はない。
したがって、頂点 $3$ から辿れる辺の最大本数は $0$ である。

頂点 $1$ からは頂点 $3$ へ進める。
その先ではもう辺を辿れないので、最大本数は $1$ である。

頂点 $2$ からは、頂点 $1$ または頂点 $3$ へ進める。
頂点 $1$ へ進む場合は、そこからさらに $1$ 本辿れる。
したがって、合計 $2$ 本辿れる。

頂点 $3$ へ進む場合は、合計 $1$ 本である。
よって、頂点 $2$ から辿れる辺の最大本数は $2$ となる。

頂点 $0$ からは、頂点 $1$ または頂点 $2$ へ進める。
頂点 $1$ へ進む場合は、合計 $2$ 本辿れる。
頂点 $2$ へ進む場合は、合計 $3$ 本辿れる。

したがって、頂点 $0$ から辿れる辺の最大本数は $3$ となる。

各頂点についてまとめると、次のようになる。

全頂点の最大値は $3$ なので、答えは $3$。

注意点

特になし。

別解

メモ化再帰による深さ優先探索で、全頂点から探索しても解ける。
DP コンテストの意図からは外れるが。