はまやんはまやんはまやん

hamayanhamayan's blog

Longest Path [Educational DP Contest / DP まとめコンテスト G]

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としているのはパスが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;
}