Longest path on DAG
(Mylib/Graph/DAG/dag_longest_path.cpp)
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