Longest path on DAG
(Mylib/Graph/DAG/dag_longest_path.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Code

#pragma once
#include <algorithm>
#include <vector>

namespace haar_lib {
  int dag_longest_path(const std::vector<std::vector<int>> &g) {
    const int n = g.size();
    std::vector<int> ret(n);
    std::vector<bool> visited(n);

    auto dfs =
        [&](auto &f, int cur) -> int {
      if (visited[cur]) return ret[cur];
      visited[cur] = true;

      for (auto &nxt : g[cur]) {
        ret[cur] = std::max(ret[cur], f(f, nxt) + 1);
      }

      return ret[cur];
    };

    for (int i = 0; i < n; ++i)
      if (not visited[i]) dfs(dfs, i);

    return *std::max_element(ret.begin(), ret.end());
  }
}  // namespace haar_lib

#line 2 "Mylib/Graph/DAG/dag_longest_path.cpp"
#include <algorithm>
#include <vector>

namespace haar_lib {
  int dag_longest_path(const std::vector<std::vector<int>> &g) {
    const int n = g.size();
    std::vector<int> ret(n);
    std::vector<bool> visited(n);

    auto dfs =
        [&](auto &f, int cur) -> int {
      if (visited[cur]) return ret[cur];
      visited[cur] = true;

      for (auto &nxt : g[cur]) {
        ret[cur] = std::max(ret[cur], f(f, nxt) + 1);
      }

      return ret[cur];
    };

    for (int i = 0; i < n; ++i)
      if (not visited[i]) dfs(dfs, i);

    return *std::max_element(ret.begin(), ret.end());
  }
}  // namespace haar_lib

Back to top page