一：本题意：给定一张包含 n 个生物、m 条捕食关系的食物网，可形式化为一张有向无环图（DAG）。每条有向边由一对整数 v,u 表示：生物 u 捕食生物 v。

（1）起点是生产者：不会捕食其它生物，即在图中出度为 0 的节点

（2）终点是顶级消费者：不会被其它生物捕食，即在图中入度为 0 的节点

问题：求请计算图中这样的食物链共有多少条 二：分析思虑：

1：从题意可知，该食物链构成了一个天然的图结构，因此需要考虑使用邻接表。

2：问题提到计算途中的食物链有多少条，那就直接求顶级猎食者到各底层猎物的总路径，考虑使用后续递归遍历。在后续递归遍历中，父节点的食物链是所有子节点的食物链的和，因此考虑使用动态规划。

3：由于求所有顶级猎食者的食物链，所有需要获得所有顶级猎食者，最后的答案是所有顶级猎食者的食物链之和。

三：解法： 1：定义图的存储结构adj，每个adj[u]表示猎食者的所有猎物。

2：定义dp，dp[i]表示猎食者i的食物链数量,起始时赋初值为-1，表示该猎食者食物链数量还未获得。

3：hasPredator判断i是否有猎物，如果为false，则表明是顶级猎食者，hasPrey判断是否有猎物，如果为false,表明是生产者。

4：定义dfs算法，计算每个猎食者的食物链数量，dp[u]：

（1）边界条件：如果dp[u]!=-1,返回；如果是生产者则令dp[u]=1，然后返回;

（2）递推过程：猎食者u的食物链是所有猎物的食物连之和。

5：具体过程：

（1）对每个顶级猎食者调用dfs算法，并求和，此结果既为所有猎食者的食物链，但是需要排除一种情况。

（2）由于在深度递归中将所有既是顶级猎食者又是生产者的节点dp[u]初值设置为1，但是该情况与题意不符，所以减去。

#include <iostream>
#include <vector>
using namespace std;
//定义存储结构
vector<vector<int>> adj;
//定义dp
vector<int> dp;
//定义判断顶级猎食者标记
vector<bool> hasPredator;
//定义判断是否是消费者
vector<bool> hasPrey;
void dfs(int u){
    if(dp[u] != -1){
        return;
    }
    if(adj[u].empty()){
        dp[u]=1;
        return;
    }
    dp[u]=0;
    for(int v:adj[u]){
        dfs(v);
        dp[u]+=dp[v];
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    adj.resize(n+1);
    dp.resize(n+1,-1);
    hasPredator.resize(n+1,false);
    hasPrey.resize(n+1,false);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>v>>u;
        adj[u].push_back(v);
        hasPredator[v]=true;
        hasPrey[u]=true;
    }
    vector<int> topPredators;
    for(int i=1;i<=n;i++){
        if(hasPredator[i]==false){
            topPredators.push_back(i);
        }
    }
    int ans=0;
    for(int u:topPredators){
        dfs(u);
        ans+=dp[u];
    }
    for (int i = 1; i <= n; i++) {
        if (!hasPredator[i] && !hasPrey[i]) {
            // 既是顶级消费者（没有捕食者）又是生产者（没有食物）
            ans--;  // 减去1
        }
    }
    cout<<ans<<endl;
    return 0;
}