EDPC G - Longest Path

考え方

ABCでいうと、E問題級。

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

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

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

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

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

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

入力例1での動作

入力を受け取り、0-indexed の隣接リストにする。

graph[0]: {1, 2}
graph[1]: {3}
graph[2]: {1, 3}
graph[3]: {}

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

vec: {0, 2, 1, 3}

これを逆順にしてから使う。

vec: {3, 1, 2, 0}

dp[i] を、頂点 i から始めて最大で何本の辺を辿れるかとする。
最初は全て $0$ で初期化する。

dp: {0, 0, 0, 0}

頂点 3 を見る。
頂点 3 から出る辺はないので、更新はない。

dp: {0, 0, 0, 0}

頂点 1 を見る。
辺 1 -> 3 があるので、dp[1] を dp[3]+1 = 1 に更新する。

dp: {0, 1, 0, 0}

頂点 2 を見る。
辺 2 -> 1 があるので、dp[2] を dp[1]+1 = 2 に更新する。
また、辺 2 -> 3 もあるが、こちらは dp[3]+1 = 1 なので最大値は変わらない。

dp: {0, 1, 2, 0}

頂点 0 を見る。
辺 0 -> 1 があるので、dp[0] を dp[1]+1 = 2 に更新する。
また、辺 0 -> 2 があるので、dp[0] を dp[2]+1 = 3 に更新する。

dp: {3, 1, 2, 0}

DP テーブル内の最大値 $3$ が答え。

注意点

特になし。

別解

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