1 条题解

  • 0
    @ 2026-11-12 21:48:40

    [G] Longest Path(dp_g)题解

    题意简述

    给一张 NN 点 MM 边的 DAG,求最长有向路径的边数。

    思路

    状态

    设 fuf_u = 从 uu 出发能走的最长路径长度(边数)。则

    $$f_u = \max_{(u,v)\in E} \left( f_v + 1 \right),\qquad \text{无边时 } f_u = 0.$$

    答案 max⁡ufu\max_u f_u。

    计算顺序

    DAG 上求这个式子,可以:

    • 拓扑排序 + 逆序递推:对拓扑序从后往前扫,fuf_u 的所有后继 vv 已经在拓扑序后面算完了;
    • 或记忆化 DFS。

    本题 N,M≤105N,M \le 10^5,要注意:

    1. 记忆化 DFS 在链状图上递归深度可达 10510^5,C++ 默认栈可能爆掉——要么拓扑排序写迭代,要么 #pragma comment(linker, "/STACK:...")(不通用)。推荐拓扑排序。
    2. 图不连通是允许的(样例 2 就是)。

    复杂度

    时间 O(N+M)O(N+M),空间 O(N+M)O(N+M)。

    参考代码

    #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;
    }
    

    易错点

    1. 递归爆栈:链状 DAG 深度 10510^5,记忆化递归需谨慎。
    2. 答案为 00 的情况:所有边都不构成更长的路(如 N=2N=2 只有边 2→12\to1,最长路长为 11;若 MM 条边全孤立则答案 ≥1\ge1)。注意"单点路径"不算边,答案是最长边数。
    3. 输入可能有重边吗?题目保证所有 (xi,yi)(x_i,y_i) 互不相同,但仍建议用邻接表按输入直接建图。

    数据说明

    共 14 组:3 组官方样例;链、反链(i+1→ii+1 \to i,检验拓扑序方向)、随机 N=6/20/200N=6/20/200 的 DAG、N=1000N=1000 随机、N=105N=10^5 随机 M=105M=10^5、N=105N=10^5 的长链(深度 10510^5,专门卡递归爆栈)、N=105N=10^5 的反向长链。

    • 1

    信息

    ID
    16
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者