まずグラフを強連結成分分解（SCC）します。 ここで、すべての頂点へ行ける超頂点 \(s\) とすべての頂点から行ける超頂点 \(t\) を追加しておくと、 \(s\) から \(t\) への path だけを考えれば良くなり、遷移の場合分けがラクになります（実装によっては最後に \(2\) だけ引く必要があります）。 超頂点も含め SCC 後のグラフをトポロジカルソート順に並べ、新たに頂点 \(1\) から 頂点 \(M\) としておきます。

さて \(i\) と \(j\) で終わる2つの path が通る頂点の数の最大値を \({\rm dp}[i][j]\) とすると、例えば下式のように更新できます。

\(\displaystyle {\rm dp}[i][j] = \max_{k \in E_i} \big\{{\rm dp}[j][k]\big\} + {\rm size}(i)\ (j<i)\)

\(\displaystyle {\rm dp}[i][i] = \max_{j,\ k \in E_i} \big\{{\rm dp}[j][k]\big\} + {\rm size}(i)\)

ここで \({\rm size}(i)\) は頂点 \(i\) の SCC 前のグラフでの頂点数、 \(E_i\) は頂点 \(i\) に向かう辺がある頂点全体の集合です。

\({\rm dp}[M][M]\) が求めるものです。これは小さい方から順に更新することで、全体で \(O(N^3)\) で計算できます。