采用反向记忆化 DFS的思路，统计 DAG 上符合题目定义的食物链数量，核心逻辑如下：

  1. 明确题目定义与代码的对应关系题目要求的食物链是：生产者（出度为0，起点） → 沿有向边 → 顶级消费者（入度为0，终点）。代码采用反向统计的思路，从终点（入度为 0 的顶级消费者）出发，反向遍历到起点（出度为 0 的生产者），路径总数与正向统计完全一致。
  2. 图的构建与初始化用邻接表存储题目给出的有向边，同时统计每个节点的入度，用于后续筛选顶级消费者（终点）。dp数组初始化为 1，代表每个节点自身是路径的基础单元；有出边的节点会被标记为 0，既表示该节点不是生产者（起点），也标记为未计算状态，用于记忆化递归。
  3. 记忆化 DFS 实现路径计数递归函数dfs(x)的含义：计算从节点x出发，沿有向边能到达的所有生产者（起点）的路径总数。递归逻辑：遍历当前节点的所有后继节点，若后继节点未计算则先递归计算，再累加结果；若已计算则直接复用结果，避免重复递归，保证时间复杂度为 O (n+m)，适配 1e5 的数据规模。
  4. 合法结果的统计遍历所有入度为 0 的节点（题目定义的顶级消费者、食物链终点），跳过无入边也无出边的孤立节点（无法构成有捕食关系的食物链）。对每个合法的终点调用 DFS，累加所有路径数，得到最终的食物链总数。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;

vector<vector<ll>> adj(N); // 邻接表，存储有向边u->v
ll in[N];                   // 入度数组，统计每个节点的入度
vector<ll> dp(N, 1);       // dp[x]：从x出发到合法起点的路径数，初始默认自身为1条基础路径


// 记忆化DFS：计算从x出发，能到达的所有合法起点的路径总数
ll dfs(ll x) {
    // 遍历当前节点x的所有后继节点t
    for (auto t : adj[x]) {
        // 若t的路径数未计算（dp[t]==0），先递归计算t的路径数再累加
        if(dp[t]==0)dp[x]+=dfs(t);
        // 若t的路径数已计算完成，直接累加结果
        else dp[x]+=dp[t];
    }
    return dp[x]; // 返回当前节点x的总路径数
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 加速输入输出
    ll n,m;
    cin>>n>>m; // 输入生物数量n、捕食关系数量m
    
    for(ll i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        adj[u].push_back(v); // 建边u->v，对应题目中v捕食u的关系
        dp[u]=0;             // 有出边的节点，标记为未计算状态，且非路径起点
        in[v]++;             // 统计节点v的入度
    }

    ll ans=0; // 存储最终的食物链总数

    for(ll i=1;i<=n;i++){
        if(in[i]==0&&dp[i]==1)continue; // 跳过孤立节点（无入边无出边，不构成合法食物链）
        if(in[i]==0){                    // 从入度为0的顶级消费者（题目定义的终点）开始计算
            ans+=dfs(i);                 // 累加该终点对应的所有合法食物链数量
        }
    }

    cout<<ans; // 输出最终结果
    return 0;
}