Description
首先明确，最大食物链指生产者到顶级消费者（即最高营养级），而不是最长的食物链
这样，我们就可以将题意转化为：
在一张图中，求入度为0的点到出度为0的点路径数量
这不妥妥的拓扑排序嘛（这题竟然在dp训练题单里，想了好久的dp）
Solution
虽说是拓扑排序，但并不完全是。
我们先回忆一下拓扑排序是如何进行的：
- 找到一个入度为0的点
- 删除与这个点连接的点
- 继续找入度为0的点
对于这道题，我们显然不能删边，直接dfs搜索即可。
但是直接dfs复杂度太高，需要记忆化一下，记录每个点作为底的路径个数，若搜索到出度为0的点则返回1（代表一个路径）
显然我们只需要对刚开始入度为0的点dfs（拓扑排序，因为生产者的入度为0），题意明确了就比较明了。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 5000000
#define mod 80112002
using namespace std;
int in[N],out[N];
vector <int> Edge[N];
int n,m;
int rem[N];
int ans = 0;
int dfs(int x)
{
if(rem[x]) return rem[x]; //记忆化
if(!out[x]) return 1; //如果出度为0则代表一条路径
int sum = 0;
for(int i=0;i<Edge[x].size();i++)
{
sum += dfs(Edge[x][i]); //记录当前节点为底的路径数量
sum %= mod; //能%就%一下吧，防止炸
}
rem[x] = sum%mod;//同上
return sum;//返回该点为底路径的数量即可
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Edge[x].push_back(y);
out[x] ++; //记录入度出度
in[y] ++;
}
for(int i=1;i<=n;i++)
{
if(!in[i]) //只需要对入度为0的点拓扑排序即可
{
ans +=dfs(i);
ans %= mod;
}
}
cout<<ans%mod<<endl;
return 0;
}