题目描述

给定一个包含 个生物和 条捕食关系的食物网，这可以被看作一个有向无环图 (DAG)。每条有向边由一对整数 表示：生物 捕食生物 ，形成一条有向边 。

题目对“食物链”的定义如下：

  • 起点是生产者：不会捕食其它生物，即在图中出度为 0 的节点。
  • 终点是顶级消费者：不会被其它生物捕食，即在图中入度为 0 的节点。
  • 路径需要沿有向边（捕食方向）从起点连接到终点。

题目保证最终答案不超过 。

解题思路

1. 题意分析

题目的描述存在一个核心的逻辑矛盾：食物链的起点被定义为“出度为0”的节点，但路径又必须“沿有向边方向”进行。一个出度为0的节点没有任何出边，因此不可能沿有向边到达任何其他节点。

为了解决这个矛盾，我们必须重新解读题意。唯一合理的解释是：食物链的计数方向与图中定义的捕食方向（能量流动方向）相反。因此，我们的解法将基于在反向图上寻找路径。

正确的解题模型：

  1. 起点：原图中所有出度为 0 的节点（生产者）。
  2. 终点：原图中所有入度为 0 的节点（顶级消费者）。
  3. 路径：在反向图上，从起点到终点的路径。

2. 算法设计：反向图上的拓扑排序 DP

该问题可以转化为，在反向图上统计从特定起点集合到特定终点集合的路径总数。这是一个可以在 DAG 上通过拓扑排序和动态规划解决的经典问题。

  • 状态定义: 表示在反向图中，从所有“生产者”节点出发，到达节点 的路径总数。

  • 图的构建:

    • 我们需要根据输入构建一个反向图的邻接表 adj_rev。如果输入 表示原图存在边 ，我们就在反向图中添加边 。
    • 同时，我们仍然需要计算原图的入度 in_degree_orig 和出度 out_degree_orig，以便识别出“顶级消费者”和“生产者”。

  • 初始化:

    • 在反向图中，拓扑排序的起始节点是入度为0的节点。一个节点在反向图中的入度，等于它在原图中的出度。
    • 因此，我们找到所有在原图中出度为 0 的节点（生产者），将它们作为拓扑排序的初始节点加入队列。
    • 对于这些生产者节点 ，它们的 值初始化为 1。

  • 状态转移:

    • 我们对反向图执行标准的拓扑排序 (Kahn's algorithm)。
    • 当从队列中取出一个节点 时，遍历它在反向图中的所有邻居 。
    • 到达 的路径数可以由到达 的路径数转移而来，所以我们执行累加：。
    • 更新 在反向图中的入度，当入度变为 0 时将其入队。

  • 统计答案:

    • 拓扑排序结束后，我们遍历所有节点。如果一个节点 在原图中的入度为 0（即为顶级消费者），我们就将 的值累加到最终答案中。

  • 特殊情况：零长路径:

    • 题目要求食物链需要“依次连接”，这通常意味着路径的长度至少为1（即至少包含一条边）。
    • 在我们的计算中，如果一个节点 既是生产者（原图出度为0）又是顶级消费者（原图入度为0），它会作为一个起点被初始化 ，又会作为一个终点被计入答案。这实际上是统计了一条从 到自身的零长路径。
    • 因此，在累加答案时，如果发现一个终点同时也是起点，需要将结果减1，以排除这种情况。

代码实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj_rev(n + 1);
    vector<int> in_degree_orig(n + 1, 0);
    vector<int> out_degree_orig(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 构建反向图
        adj_rev[v].push_back(u);
        // 记录原图的度
        out_degree_orig[u]++;
        in_degree_orig[v]++;
    }

    queue<int> q;
    vector<long long> dp(n + 1, 0);
    // 反向图的入度等于原图出度
    vector<int> in_degree_topo = out_degree_orig;

    // 初始化队列和dp数组，起点是原图出度为0的节点（生产者）
    for (int i = 1; i <= n; ++i) {
        if (in_degree_topo[i] == 0) {
            q.push(i);
            dp[i] = 1;
        }
    }

    // 在反向图上进行拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj_rev[u]) {
            dp[v] += dp[u];
            if (--in_degree_topo[v] == 0) {
                q.push(v);
            }
        }
    }

    long long total_chains = 0;
    // 终点是原图入度为0的节点（顶级消费者）
    for (int i = 1; i <= n; ++i) {
        if (in_degree_orig[i] == 0) {
            total_chains += dp[i];
            // 如果该顶级消费者同时也是生产者，说明计入了一条长度为0的路径
            // 题目要求“依次连接”，意味着路径长度至少为1，需减去此情况
            if (out_degree_orig[i] == 0) {
                total_chains--;
            }
        }
    }

    cout << total_chains << endl;

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Integer>[] adjRev = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adjRev[i] = new ArrayList<>();
        }
        int[] inDegreeOrig = new int[n + 1];
        int[] outDegreeOrig = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            // 构建反向图
            adjRev[v].add(u);
            // 记录原图的度
            outDegreeOrig[u]++;
            inDegreeOrig[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        long[] dp = new long[n + 1];
        // 反向图的入度等于原图出度
        int[] inDegreeTopo = outDegreeOrig.clone();

        // 初始化队列和dp数组，起点是原图出度为0的节点（生产者）
        for (int i = 1; i <= n; i++) {
            if (inDegreeTopo[i] == 0) {
                q.add(i);
                dp[i] = 1;
            }
        }

        // 在反向图上进行拓扑排序
        while (!q.isEmpty()) {
            int u = q.poll();

            for (int v : adjRev[u]) {
                dp[v] += dp[u];
                inDegreeTopo[v]--;
                if (inDegreeTopo[v] == 0) {
                    q.add(v);
                }
            }
        }

        long totalChains = 0;
        // 终点是原图入度为0的节点（顶级消费者）
        for (int i = 1; i <= n; i++) {
            if (inDegreeOrig[i] == 0) {
                totalChains += dp[i];
                // 如果该顶级消费者同时也是生产者，说明计入了一条长度为0的路径
                // 题目要求“依次连接”，意味着路径长度至少为1，需减去此情况
                if (outDegreeOrig[i] == 0) {
                    totalChains--;
                }
            }
        }
        
        System.out.println(totalChains);
    }
}

import sys
from collections import deque

def main():
    line = sys.stdin.readline()
    if not line.strip():
        return
    n, m = map(int, line.split())

    adj_rev = [[] for _ in range(n + 1)]
    in_degree_orig = [0] * (n + 1)
    out_degree_orig = [0] * (n + 1)

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        # 构建反向图
        adj_rev[v].append(u)
        # 记录原图的度
        out_degree_orig[u] += 1
        in_degree_orig[v] += 1
    
    q = deque()
    dp = [0] * (n + 1)
    # 反向图的入度等于原图出度
    in_degree_topo = list(out_degree_orig)

    # 初始化队列和dp数组，起点是原图出度为0的节点（生产者）
    for i in range(1, n + 1):
        if in_degree_topo[i] == 0:
            q.append(i)
            dp[i] = 1
    
    # 在反向图上进行拓扑排序
    while q:
        u = q.popleft()
        for v in adj_rev[u]:
            dp[v] += dp[u]
            in_degree_topo[v] -= 1
            if in_degree_topo[v] == 0:
                q.append(v)
        
    total_chains = 0
    # 终点是原图入度为0的节点（顶级消费者）
    for i in range(1, n + 1):
        if in_degree_orig[i] == 0:
            total_chains += dp[i]
            # 如果该顶级消费者同时也是生产者，说明计入了一条长度为0的路径
            # 题目要求“依次连接”，意味着路径长度至少为1，需减去此情况
            if out_degree_orig[i] == 0:
                total_chains -= 1
            
    print(total_chains)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 拓扑排序, 动态规划 (在反向图上)
  • 时间复杂度: ，其中 是生物数量， 是捕食关系数量。建图、计算度、拓扑排序都需要线性的时间。
  • 空间复杂度: ，用于存储反向图的邻接表、原图的入度和出度数组、拓扑排序用的度数组以及DP数组。