今日题目：食物链
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 11 秒的时间。
由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。
输入格式
第一行，两个正整数 n、m，表示生物种类 n 和吃与被吃的关系数 m。
接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出格式
一行一个整数，为最大食物链数量模上 80112002 的结果。
题目分析
题目难度：⭐️⭐️⭐️
题目涉及算法：拓扑排序，记忆化搜索。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
拓扑排序的板子，数据范围不大所以开了个二维数组哈哈哈，第二个是记忆化搜索
2.代码
#include<bits/stdc++.h> using namespace std; const int N = 5005; int n,m,ru[N],chu[N],a,b,f[N],ans; int mp[N][N]; queue<int>q; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>a>>b; mp[a][b]=1; chu[a]++; ru[b]++; } for(int i=1;i<=n;i++) { if(ru[i]==0) { f[i]=1; q.push(i); } } while(!q.empty()) { int a=q.front(); q.pop(); for(int k=1;k<=n;k++) { if(mp[a][k]==0) { continue; } f[k]+=f[a]; f[k]%=80112002; ru[k]--; if(ru[k]==0) { if(chu[k]==0) { ans+=f[k]; ans%=80112002; continue; } q.push(k); } } } cout<<ans; }
记忆化搜索：
一共五条食物链 ，通过对图观察能够发现一条完整的食物链最高级消费者是没有被吃过的，而生产者和低级别的消费者是会被吃过，所以可以设置两个标记数组来表示被吃过与吃过的。
创建了这两个数组之后我们就要着手将他们的关系存下来了，因此我们可以创建一个结构体数组用来表示吃与被吃的关系，然后选择找到相对的关系而不是循环遍历，就能避免tle
#include<bits/stdc++.h> using namespace std; const int N = 5005; int n,m,c[N]; int w[N],u[N],ans,c2[N]; int j=1; struct node{ int x,y,next; }mp[500005]; int dfs(int t) { int num=0; if(!u[t]) { return 1; } if(c[t]) { return c[t]; } for(int i=c2[t];i;i=mp[i].next) { (num+=dfs(mp[i].x))%=80112002; } return c[t]=num; } int main() { cin>>n>>m; while(m--) { int a,b; cin>>a>>b; w[a]=1; u[b]=1; mp[j].x=a; mp[j].y=b; mp[j].next=c2[b]; c2[b]=j; j++; } for(int i=1;i<=n;i++) { if(!w[i]) { (ans+=dfs(i))%=80112002; } } cout<<ans; }
