题解 | #食物链计数#

拓扑排序 + 动态规划

对于 DAG 上的路径统计问题，动态规划是最优解法。由于图的拓扑序保证了状态的前后依赖关系，结合拓扑排序可以高效地递推状态。

1. 状态定义

定义 $dp[i]$ 为：从任意一个顶级消费者（入度为 0 的起始点）出发，到达生物节点 $i$ 的路径条数。

2. 状态转移方程

对于每个节点 $v$ ，其路径条数等于所有能捕食它（方向是 $u \to v$ ，即所有指向它的节点 $u$ ）的节点路径条数之和： $dp[v] = \sum_{(u, v) \in E} dp[u]$

3. 初始条件

若节点 $i$ 的入度为 0 且出度不为 0（即非孤立点的顶级消费者），初始化 $dp[i] = 1$ 。
孤立节点（入度为 0 且出度也为 0）不构成生物学意义上的“链”，通常不计入统计（或根据题意特殊处理，本题逻辑中若 $m > 0$ ，孤立点不会产生有效贡献）。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<vector<int>> adj(n + 1);
    vector<int> in(n + 1, 0), out(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        out[u]++;
        in[v]++;
    }

    queue<int> Q;
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0 && out[i] > 0) {
            Q.push(i);
            dp[i] = 1;
        }
    }

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : adj[u]) {
            dp[v] += dp[u];
            in[v]--;
            if (in[v] == 0) {
                Q.push(v);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (out[i] == 0) {
            ans += dp[i];
        }
    }

    cout << ans << endl;
}

复杂度分析

1. 时间复杂度： $O(N + M)$

建图：遍历所有边 $M$ ，时间 $O(M)$ 。
初始化：遍历所有点 $N$ ，时间 $O(N)$ 。
拓扑排序与 DP：每个节点入队出队一次，每条边被松弛（转移）一次，总时间 $O(N + M)$ 。

2. 空间复杂度： $O(N + M)$

存储图：邻接表占用 $O(N + M)$ 。
辅助数组：入度数组、出度数组、DP 数组各占用 $O(N)$ 。