ノードを消していく発想（もしくは、トポロジカルオーダーによる処理）
前回のアルゴリズムの計算量を考えてみましょう。
for x in range(1, N+1): for y in range(1, N+1): if dp[y][x] == 0: continue for z in range(1, N+1): if dp[x][z] == 0: continue
この3重ループからわかる様に最悪ケースで です。大部分の dp[x][y]、dp[y][z] が 0 であれば、リンク情報を別のデータ構造に持たせた、
for x in range(1, N+1): for y in L_to[x]: for z in L_from[x]: dp[y][z] = max(dp[y][z], dp[y][x] + dp[x][z]) if y not in L_to[z]: L_to[z].append(y) # リンク情報の更新に注意 L_from[y].append(z) # リンク情報の更新に注意
こちらのパターンで改善する気もしますが、そういうわけでもありません。「リンク情報の更新に注意」とコメントがあるように、1つのノードを処理するたびに、リンクの数はどんどん増えていくのです。最初に与えられたリンクが少ないからといって、リンクに関するループの回数も同じ様に少なくなるわけではないのですよね。
とは言え、ここに改善のヒントがあります。
ノードを処理するごとにリンクが増えてこまるわけですが、実は、処理をしてもリンクが増えないノードがあります。
それは・・・
「他のノードからのリンクを持たず、自身からのリンクだけを持つノード（始ノード）」
です。（反対の「終ノード」も同様ですが、そちらは今は置いておきます。）
このノード x は上述のコードの処理をしても何も変化がおきません。ただし、今回の問題に関しては、始ノードは、とても重要な役割をもちます。なぜなら、
・最終的に最長経路を与えるパスは、始ノードからはじまる（そして、終ノードでおわる）
と言うことが確実にわかっているからです。
始ノードが複数ある場合は、それらのどれか1つが最長パスの始点になるはずです。したがって、最長経路を発見したければ、まずは、始ノードを見つけて、そこから探索を始めればよいのです。
たとえば、始ノード x からリンクされているノード y に対して、始ノードからの距離が1である（つまり最長パスにおける2ノード目である）、という情報を記録します。ただし、ノード y に対して、始ノード x 以外のノードからのリンクがある場合、そちらを経由してまわってくる可能性があので、本当に最長パスにおける2ノード目になるかはまだ分かりません。
なのですが・・・・、逆に言えば、y に入るリンクが x からのものだけであれば、始ノードからの距離が1であるという情報はここで確定します。これをはっきりさせるためには、始ノード x をもぎ取って捨ててしまえばOKです。そうです。すべての始ノードを削除した状況を想像してください。
この状態における新たな始ノードを見つけ出せば、そこからリンクされているノードに対して、始ノードからの距離は2である、という情報が記録できます。このようにして、
(1) 始ノードを探索して、すべての始ノード対して処理する
(2) 処理した始ノードを捨てる
(3) (1) に戻る
というループを繰り返せば、ノードを1つずつ減らしながら、確実に答えに近づいていくことができます。（ちなみに、こういう順序でグラフを処理することを「トポロジカルオーダーで処理する」とか言ったりもします。）ノード x に対して、始ノードからの距離までの距離を dp[x] に記録することにして、次の様な実装ができます。
dp = [0]*(N+1) L_from = [[] for _ in range(N+1)] in_count = [0]*(N+1) for _ in range(M): x, y = # 始点 x、終点 y を読み込み in_count[y] += 1 L_from[x].append(y) queue = [x for x in range(1, N+1) if in_count[x] == 0] while len(queue) > 0: x = queue.pop() for y in L_from[x]: dp[y] = max(dp[y], dp[x] + 1) # ---- (*) in_count[y] -= 1 if in_count[y] == 0: queue.append(y) print(max(dp))
ここでは、それぞれのノードに対して、外部から入ってくるリンク数 in_count を保持しておき、「始ノードを捨てる」という処理をこのリンク数を減らすという処理に対応させています。queue は、これから処理するべき始ノードを保持したキュー（実際にはスタックとして使ってますが。。。）で、新たに発生した始ノードを順次追加していき、このキューが空になれば計算終了です。残った dp[ ] の最大値が求める答えになります。
なお、(*) で dp[y] を更新する所で、既存の値との max をとっている点に注意してください。始ノードから y に至る経路が複数ある場合に、より長い経路を選択するためです。
これで無事にパスするコードが完成しました。
「始ノードから順番に処理する」というテクニックがミソでしたね。
おまけ
上でちらっと触れた様に、この実装では、queue をスタックとして使ってしまっているので、後から生まれた「始ノード」の方が最初からあった「始ノード」より先に処理されます。これは、厳密な意味でのトポロジカルオーダーにはなりません。（厳密なトポロジカルオーダーを「幅優先探索」とすれば、こちらは、「深さ優先探索」のようなものですね。）
この問題の場合は、このままでも構いませんが、厳密にトポロジカルオーダーで処理する必要がある場合は、queue を先入れ先出しのキューとして使ってください。ただし、queue.pop(0) はキューが長くなると処理が遅くなるので、collections ライブラリーの deque を使ってあげてください。
from collections import deque q = deque() for x in range(1, N+1): if in_count[x] == 0: q.append(x) while q: x = q.popleft() for y in L_from[x]: dp[y] = max(dp[y], dp[x] + 1) # ---- (*) in_count[y] -= 1 if in_count[y] == 0: q.append(y)
この次は、下記の記事を読むと良いでしょう。
