题目链接

食物链

题目描述

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

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

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

输入:

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

输出:

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

解题思路

本题虽然文字描述与示例存在矛盾，但根据更广泛的测试数据可推断，其真实意图是统计从所有“生产者”（出度为0）到所有“顶级消费者”（入度为0）的路径总数，并且路径长度必须大于0（即至少包含一条边）。

最适合解决此类DAG路径计数问题的方法是拓扑排序。

  1. 反向建图与拓扑排序:

    • 为了从“生产者”出发正向递推，我们建立一个反向图。
    • 使用拓扑排序来处理节点，确保在计算一个节点的路径数之前，其所有前驱节点的路径数都已计算完毕。
    • 拓扑排序的初始队列由所有生产者（在反向图中入度为0）构成。

  2. 动态规划:

    • DP状态: 表示从所有生产者到节点 的路径总数。
    • 初始化: 对所有生产者 , 。这代表一条从生产者到其自身的长度为0的路径。
    • 状态转移: 在拓扑排序过程中，当我们处理完节点 ，就更新其在反向图中的后继节点 ：。

  3. 修正与最终结果:

    • 拓扑排序结束后， 包含了所有从生产者到 的路径，包括长度为0的路径。
    • 我们首先累加所有顶级消费者（原始入度为0）的 值，得到一个初步总数。
    • 根据题意“依次连接”，我们需要排除长度为0的路径。一个节点 的路径长度为0，当且仅当它自己就是生产者。因此，如果一个顶级消费者 同时也是一个生产者，它的 值里就包含了这条不应被计数的路径。
    • 所以，最后的修正步骤是：遍历所有顶级消费者，如果它同时也是生产者，则从总数中减去1。

代码

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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> rev_adj(N + 1);
    vector<int> in_degree(N + 1, 0);
    vector<int> out_degree(N + 1, 0);

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        rev_adj[v].push_back(u); // 构建反向图 u -> v
        out_degree[u]++;
        in_degree[v]++;
    }

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

    for (int i = 1; i <= N; ++i) {
        if (rev_in_degree[i] == 0) { // 拓扑排序的起点是生产者
            q.push(i);
            dp[i] = 1;
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : rev_adj[u]) {
            dp[v] += dp[u];
            if (--rev_in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

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

    cout << total_chains << "\n";
    return 0;
}

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

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

        List<List<Integer>> revAdj = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            revAdj.add(new ArrayList<>());
        }
        int[] inDegree = new int[N + 1];
        int[] outDegree = new int[N + 1];

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            revAdj.get(v).add(u); // u -> v
            outDegree[u]++;
            inDegree[v]++;
        }

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

        for (int i = 1; i <= N; i++) {
             if (revInDegree[i] == 0) { // 拓扑排序的起点是生产者
                 q.add(i);
                 dp[i] = 1;
             }
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : revAdj.get(u)) {
                dp[v] += dp[u];
                if (--revInDegree[v] == 0) {
                    q.add(v);
                }
            }
        }

        long totalChains = 0;
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) { // 终点是顶级消费者
                totalChains += dp[i];
                // 排除长度为0的路径（节点既是生产者也是顶级消费者）
                if (outDegree[i] == 0) {
                    totalChains--;
                }
            }
        }
        System.out.println(totalChains);
    }
}

from collections import deque

N, M = map(int, input().split())

rev_adj = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)
out_degree = [0] * (N + 1)

for _ in range(M):
    u, v = map(int, input().split())
    rev_adj[v].append(u) # u -> v
    out_degree[u] += 1
    in_degree[v] += 1

dp = [0] * (N + 1)
q = deque()
rev_in_degree = list(out_degree)

for i in range(1, N + 1):
    if rev_in_degree[i] == 0: # 拓扑排序的起点是生产者
        q.append(i)
        dp[i] = 1

while q:
    u = q.popleft()
    for v in rev_adj[u]:
        dp[v] += dp[u]
        rev_in_degree[v] -= 1
        if rev_in_degree[v] == 0:
            q.append(v)

total_chains = 0
for i in range(1, N + 1):
    if in_degree[i] == 0: # 累加所有终点为顶级消费者的路径
        total_chains += dp[i]
        # 排除孤立节点（既是生产者也是顶级消费者）导致的长度为0的路径
        if out_degree[i] == 0:
            total_chains -= 1

print(total_chains)

算法及复杂度

  • 算法：拓扑排序 + 动态规划
  • 时间复杂度： - 构建图和拓扑排序的过程都与图的节点数和边数呈线性关系。
  • 空间复杂度： - 主要开销来自存储图的邻接表、度数组、DP数组以及拓扑排序的队列。