题解 | #食物链计数#

题目描述

给定一张包含 个生物和 条捕食关系的食物网 (DAG)。一条食物链被定义为从一个“生产者”到一个“顶级消费者”的、由一条或多条边构成的路径。

• 生产者: 出度为 0 的节点。
• 顶级消费者: 入度为 0 的节点。

你需要计算图中这样的食物链共有多少条。

输入:

• 第一行输入两个整数 。
• 接下来 行，输入 ，表示存在有向边 。

输出:

• 输出满足定义的食物链数量。

解题思路

1. 题意分析

我们需要计算从所有生产者（出度为 且入度不为 ）到所有顶级消费者（入度为 且出度不为 ）的路径总数。图是无环的，因此可以使用动态规划来计数路径。

关键点：

• 生产者：出度为 且入度不为 （只有被捕食，不捕食其他生物）
• 顶级消费者：入度为 且出度不为 （只捕食其他生物，不被捕食）
• 单独一个点（既无入度也无出度）不构成食物链

2. 算法设计

方法一：DFS（记忆化搜索）

从每个顶级消费者开始，沿着捕食关系的反方向进行DFS，记录每个节点到生产者的路径数：

• w[u] 表示从节点 u 到任意生产者的路径数
• 对于生产者，初始化 w[生产者] = 1
• 对于其他节点 u，w[u] = ∑ w[v]，其中 v 是 u 的后继节点（即 u 捕食 v）
• 最终答案 = 所有顶级消费者的 w 值之和

注意：虽然题目定义食物链从生产者到顶级消费者，但反过来计算路径数更简单，因为图是无环的，反向计算不影响结果。

方法二：拓扑排序（动态规划）

将图反向思考，从顶级消费者（原图入度为 0 且出度不为 0）开始，按照拓扑序计算到每个节点的路径数：

1. 找到所有入度为 0 且出度不为 0 的点（顶级消费者）作为起点，w[起点] = 1
2. 进行拓扑排序，对于每个节点 u，将其 w[u] 累加到所有后继节点 v 的 w[v] 中
3. 最后累加所有出度为 0 且入度不为 0 的点（生产者）的 w 值

代码实现

方法一：DFS（记忆化搜索）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define llf 0x3f3f3f3f3f3f3f3f
#define pll pair<int,int>
#define endl '\n'
/*
████████╗ █████╗ ███╗      ███╗███╗      ███╗██╗   ██╗
   ██╔══╝██║  ██║████╗    ████║████╗    ████║ ██╗ ██╔╝
   ██║   ██║  ██║██╔██╗  ██╔██║██╔██╗  ██╔██║  ████╔╝
   ██║   ██║  ██║██║ ██╗██╔╝██║██║ ██╗██╔╝██║   ██╔╝
   ██║    █████╔╝██║  ███╔╝ ██║██║  ███╔╝ ██║   ██║
   ╚═╝    ╚════╝ ╚═╝  ╚══╝  ╚═╝╚═╝  ╚══╝  ╚═╝   ╚═╝
███████╗██╗  ██╗███████╗██╗     ███████╗ ██╗   ██╗
██╔════╝██║  ██║██╔════╝██║     ██╔═══██╗ ██╗ ██╔╝
███████╗███████║█████╗  ██║     ███████╔╝  ████╔╝
╚════██║██╔══██║██╔══╝  ██║     ██╔═══██╗   ██╔╝
███████║██║  ██║███████╗███████║███████╔╝   ██║
╚══════╝╚═╝  ╚═╝╚══════╝╚══════╝╚══════╝    ╚═╝
*/
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

signed main() {
    int n = read(), m = read(), ans = 0;
    vector<vector<int>> a(n + 1), b(n + 1); // a[u]: u的出边，b[u]: u的入边
    vector<int> s, t, w(n + 1, 0), vis(n + 1, 0);
    
    // 读入图
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        a[u].push_back(v);
        b[v].push_back(u);
    }
    
    // 分类节点
    for (int i = 1; i <= n; i++) {
        if (b[i].size() == 0 && a[i].size() != 0) // 顶级消费者（入度为0且出度不为0）
            s.push_back(i);
        if (a[i].size() == 0 && b[i].size() != 0) { // 生产者（出度为0且入度不为0）
            t.push_back(i);
            w[i] = 1; // 生产者到自身的路径数为1
        }
    }
    
    // DFS记忆化搜索：从顶级消费者开始，反向计算到生产者的路径数
    auto dfs = [&](int fa, int u, auto dfs) -> void {
        vis[u] = 1;
        for (auto v : a[u]) { // 遍历u的出边（u捕食v）
            if (v == fa) continue;
            if (!vis[v])
                dfs(u, v, dfs);
            w[u] += w[v]; // 累加后继节点的路径数
        }
    };
    
    // 从每个顶级消费者开始DFS
    for (auto u : s) {
        vis[u] = 1;
        dfs(0, u, dfs);
    }
    
    // 累加所有顶级消费者的路径数
    for (auto x : s) {
        ans += w[x];
    }
    
    cout << ans;
    return 0;
}

方法二：拓扑排序（动态规划）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define llf 0x3f3f3f3f3f3f3f3f
#define pll pair<int,int>
#define endl '\n'
/*
████████╗ █████╗ ███╗      ███╗███╗      ███╗██╗   ██╗
   ██╔══╝██║  ██║████╗    ████║████╗    ████║ ██╗ ██╔╝
   ██║   ██║  ██║██╔██╗  ██╔██║██╔██╗  ██╔██║  ████╔╝
   ██║   ██║  ██║██║ ██╗██╔╝██║██║ ██╗██╔╝██║   ██╔╝
   ██║    █████╔╝██║  ███╔╝ ██║██║  ███╔╝ ██║   ██║
   ╚═╝    ╚════╝ ╚═╝  ╚══╝  ╚═╝╚═╝  ╚══╝  ╚═╝   ╚═╝
███████╗██╗  ██╗███████╗██╗     ███████╗ ██╗   ██╗
██╔════╝██║  ██║██╔════╝██║     ██╔═══██╗ ██╗ ██╔╝
███████╗███████║█████╗  ██║     ███████╔╝  ████╔╝
╚════██║██╔══██║██╔══╝  ██║     ██╔═══██╗   ██╔╝
███████║██║  ██║███████╗███████║███████╔╝   ██║
╚══════╝╚═╝  ╚═╝╚══════╝╚══════╝╚══════╝    ╚═╝
*/
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

signed main() {
    int n = read(), m = read(), ans = 0;
    vector<vector<int>> a(n + 1); // 出边
    vector<int> q, d(n + 1), w(n + 1, 0), s; // d: 入度，w: 路径数，s: 生产者
    
    // 读入图并计算入度
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        a[u].push_back(v);
        d[v]++;
    }
    
    // 找出顶级消费者（入度为0且出度不为0）和生产者（出度为0且入度不为0）
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0 && a[i].size() != 0) { // 顶级消费者
            q.push_back(i);
            w[i] = 1; // 起点路径数为1
        }
        if (d[i] != 0 && a[i].size() == 0) // 生产者
            s.push_back(i);
    }
    
    // 拓扑排序
    int h = 0;
    while (h < q.size()) {
        int t = q[h++];
        for (int x : a[t]) { // t捕食x，将t的路径数累加到x
            d[x]--;
            w[x] += w[t];
            if (!d[x]) q.push_back(x); // 入度为0时加入队列
        }
    }
    
    // 累加所有生产者的路径数
    for (auto x : s) {
        ans += w[x];
    }
    
    cout << ans;
    return 0;
}

方法比较

方法一（DFS）优缺点

优点：

• 思路直观，符合递归的自然思维
• 代码相对简洁

缺点：

• 递归深度可能较大，对于极端链状图可能导致栈溢出
• 需要额外的访问标记数组
• 常数开销较大

方法二（拓扑排序）优缺点

优点：

• 非递归实现，无栈溢出风险
• 按照拓扑序线性处理，效率更高
• 内存访问更连续，缓存友好

缺点：

• 需要手动维护队列和入度数组
• 逻辑相对复杂一些

复杂度分析

两种方法的时间复杂度均为 O(n + m)，每个节点和每条边都只被访问常数次。

空间复杂度均为 O(n + m)，用于存储图和辅助数组。

总结

两种方法都能正确解决问题，但拓扑排序方法在性能和稳定性上更优，特别适合处理大规模数据（）。DFS方法虽然直观，但在极端情况下存在栈溢出风险，需要谨慎使用。在实际竞赛中，推荐使用拓扑排序方法。