https://atcoder.jp/contests/dp/tasks/dp_g
前提知識
解説
https://atcoder.jp/contests/dp/submissions/3947799
トポロジカルソートを知っていれば一瞬だが、知らないと解けない。
DPというのは「ある状態を処理するときは、その状態に遷移する状態はすべて処理しきっている必要がある」
なので、
dp[i] := 有向パスの最後の頂点がiのときのパスの最長の長さ
と定義しても、頂点の処理順を決める必要がある。
閉路を含まない有向グラフ(=DAG)はパスの処理順を適切に決めると、「ある状態を処理するときは、その状態に遷移する状態はすべて処理しきっている」状態を常に満たす順番が存在する。
その順番を取得するためにトポロジカルソートをする。
あとは、その順で処理するだけ。
ある頂点cuについての遷移はすべての子供toについて
chmax(dp[to], dp[cu] + 1)
をする。
- 1としているのはパスが1つ伸びるからである。
すべての頂点についてすべての子供を処理すると、ならしO(M)となるので、全体として間に合う。
int N, M; vector<int> E[101010]; int dp[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; TopologicalSort ts(N); rep(i, 0, M) { int x, y; cin >> x >> y; x--; y--; ts.add_edge(x, y); E[x].push_back(y); } vector<int> ord; ts.sort(ord); fore(cu, ord) fore(to, E[cu]) chmax(dp[to], dp[cu] + 1); int ans = 0; rep(i, 0, N) chmax(ans, dp[i]); cout << ans << endl; }