今回はEDPCのG問題です。再帰を使う問題です。

問題

$N$ 頂点 $M$ 辺の有向グラフ $G$ がある。 $G$ の頂点は $1, 2, \cdots, N$ と番号が振られており、 $i$ 番目 $(1 \leq i \leq M)$ の有向辺は頂点 $x_{i}$ から $y_{i}$ へと張られている。

$G$ の有向パスのうち、最長のものの長さを求めよ。

条件

$2 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{5}$
$1 \leq x_{i}, y_{i} \leq N$
$(x_{i}, y_{i}) \neq (x_{j}, y_{j}) \quad (i \neq j)$
$G$ は有向閉路を含まない

考えたこと

$DP_{i}$ := 頂点 $i$ から始まる有向パスのうち、最長のものの長さ

と、とりあえずしてみることはすぐに考えられました。問題はこれをどのように求めるかです。

ここで、頂点 $u$ からの有向辺が1つのみ存在し、それが頂点 $v$ に伸びているとします。このとき、 $DP_{v}$ の値が分かっていれば、 \begin{align} DP_{u} = DP_{v} + 1 \end{align} が成立します。

ということは、頂点 $u$ から伸びている全ての有向辺について拡張させて、 \begin{align} DP_{u} = \left( \max_{v_{i} \in v} DP_{v_{i}} \right) + 1 \end{align} が成立します。

あとはこれを実装するのみですが、各頂点 $u$ について毎回伸びている辺について調べるには、あまりにも時間がかかります。

そこで、再帰的に $DP_{u}$ の値を求めることを考えます。そして頂点 $u$ について、既に $DP_{u}$ の値を調べ上げていれば、何度も計算する必要はありません。

以上から、各頂点について、既に調べたかどうかを表すbool型の配列を用意して、

すでに調べていれば、 $DP_{u}$ の値を返す
調べてなければ、再帰的に $DP_{u}$ の値を求める

という再帰関数を書けば、各辺を1回ずつ辿るのみなので、 $O(M)$ で計算できるはずです。

ソースコード

#include <bits/stdc++.h>

using namespace std;
 
int N, M;
vector <int> Graph[int(1e5+5)]; // グラフの入る配列

int DP[int(1e5+5)];
bool visited[int(1e5+5)];

// DP[num]の値を求める再帰関数
int Solve(int num){
  // もしすでに調べていればDP[num]を返す
  if (visited[num]) return DP[num];

  // 訪問済にする
  visited[num] = true;

  // numの有向辺の到着先のDPの値を順に求めていく
  int ans = 0;
  for (int next : Graph[num]){
    // 次の頂点での値 + 1 の最大値が答えになる
    ans = max(ans, Solve(next) + 1);
  }

  // DP[num] = ansということを代入し、ansの値を返す
  return DP[num] = ans;
}

int main(){
  cin >> N >> M;
  for (int i = 0; i < M; i++){
    int X, Y; cin >> X >> Y;
    Graph[X].push_back(Y);
  }

  // 頂点1から頂点Nの値までDP[i]の値を求めていく
  int ans = 0;
  for (int i = 1; i <= N; i++){
    ans = max(ans, Solve(i));
  }
  cout << ans << endl;

  return 0;
}