1 条题解
-
0
[G] Longest Path(dp_g)题解
题意简述
给一张 点 边的 DAG,求最长有向路径的边数。
思路
状态
设 = 从 出发能走的最长路径长度(边数)。则
$$f_u = \max_{(u,v)\in E} \left( f_v + 1 \right),\qquad \text{无边时 } f_u = 0.$$答案 。
计算顺序
DAG 上求这个式子,可以:
- 拓扑排序 + 逆序递推:对拓扑序从后往前扫, 的所有后继 已经在拓扑序后面算完了;
- 或记忆化 DFS。
本题 ,要注意:
- 记忆化 DFS 在链状图上递归深度可达 ,C++ 默认栈可能爆掉——要么拓扑排序写迭代,要么
#pragma comment(linker, "/STACK:...")(不通用)。推荐拓扑排序。 - 图不连通是允许的(样例 2 就是)。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<int>> g(n + 1); vector<int> indeg(n + 1, 0); for (int i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); g[x].push_back(y); indeg[y]++; } vector<int> f(n + 1, 0); queue<int> q; for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i); int ans = 0; while (!q.empty()) { int u = q.front(); q.pop(); ans = max(ans, f[u]); for (int v : g[u]) { f[v] = max(f[v], f[u] + 1); if (--indeg[v] == 0) q.push(v); } } printf("%d\n", ans); return 0; }易错点
- 递归爆栈:链状 DAG 深度 ,记忆化递归需谨慎。
- 答案为 的情况:所有边都不构成更长的路(如 只有边 ,最长路长为 ;若 条边全孤立则答案 )。注意"单点路径"不算边,答案是最长边数。
- 输入可能有重边吗?题目保证所有 互不相同,但仍建议用邻接表按输入直接建图。
数据说明
共 14 组:3 组官方样例;链、反链(,检验拓扑序方向)、随机 的 DAG、 随机、 随机 、 的长链(深度 ,专门卡递归爆栈)、 的反向长链。
- 1
信息
- ID
- 16
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者