AtCoder Educational DP Contest G問題解いてみた

今回の問題

【問題文】
N 頂点 M 辺の有向グラフ G があります。 頂点には 1, 2, ..., N と番号が振られています。
各 i (1 ≦ i ≦ M) について、i 番目の有向辺は頂点 x_i から y_i へ張られています。
G は有向閉路を含みません。

G の有向パスのうち、最長のものの長さを求めてください。
ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。

【制約】
・入力はすべて整数である。
・2 ≦ N ≦ 10^5
・1 ≦ M ≦ 10^5
・1 ≦ x_i, y_i ≦ N
・ペア (x_i, y_i) はすべて相異なる。
・G は有向閉路を含まない。

自分の回答

#include <bits/stdc++.h>
using namespace std;

int dp[100005];
vector<vector<int>> graph;

int dfs(int v) {
    if (dp[v] != -1) {
        return dp[v];
    }
    int res = 0;
    for (int u : graph[v]) {
        res = max(res, dfs(u) + 1);
    }

    return dp[v] = res; 
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        graph[x].push_back(y);
    }

    memset(dp, -1, sizeof(dp));

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));
    }

    cout << ans << endl;

    return 0;
}

解説

dp[i]をiを通るときの最長の長さにして、メモ化再起で解いた。どういう順番で更新するかわからないときはメモ化再起が便利である。ある点からいける点をすべて探索し、その点がすでに探索されていたら、メモしておいた情報を使い、探索されてなかったらそこからさらに探索を進めていく。
main関数以外使うときは、宣言を外側ですると楽。
追記memset初めて知った。