1 题目分析

首先，要知道这道题是 Topo 拓扑排序。不妨先从拓扑排序定义下手，分析题目的性质。经分析得：

食物链中的生物 —— 节点

生物之间的关系 —— 有向边

为了方便描述，我们将

不会捕食其他生物的生产者 叫做 最佳生产者

不会被其他生物捕食的消费者 叫做 最佳消费者

由于数据中不会出现环，所以 最大食物链 即左端是 最佳生产者 ，右端是 最佳消费者 的路径

而 只要最左端是最佳生产者 的路径（即最右端可以不是最佳消费者的最大食物链）我们称之为 类食物链

既然食物链中的生物可以看成节点，那么 最佳生产者 的入度一定为 0，而 最佳消费者 的出的也为 0

2 解题思路

想要找到一条最大食物链，那么这条路径的起点入度要为0，终点出度要为0。 故：

既要记录入度，还要记录出度！

现在的问题转换成了，如何找到图中所有左端点入度为0 且右端点出度为0 的路径的数量

3 题解

#include<bits/stdc++.h>
#define MAXN 5002
using namespace std;
int n,m,ind[MAXN],outd[MAXN];//顶点数，入度，出度 
vector<int>e[MAXN];//邻接表 
int num[MAXN];//记录到这个点食物链的数量
int mod=80112002;//定义最终答案mod的值 
int ans;//记录答案 
int main(){
	cin>>n>>m;
	queue<int>q;
	for(int i=1;i<=m;++i){//输入边 
		int x,y;
		cin>>x>>y;
		++ind[y],++outd[x];//右节点入度+1，左节点出度+1
		e[x].push_back(y);//建立一条单向边 
	} 
	for(int i=1;i<=n;++i){//初次寻找入度为0的点[最佳生产者] 
		if(!ind[i]){//是最佳生产者 
			num[i]=1;//初始化 
			q.push(i);//压入队列 
		}
	}
	while(!q.empty()){//还可以进行topo排序 
		int tot=q.front();//取出队首
		q.pop();//弹出
		int len=e[tot].size();
		for(int i=0;i<len;++i){//枚举这个点相邻的所有点 
			int next=e[tot][i];//取出目前枚举到的点 
			--ind[next];//将这个点的入度-1(因为目前要删除第tot个点) 
			num[next]=(num[next]+num[tot])%mod;//更新到下一个点的路径数量 
			if(ind[next]==0)
				q.push(e[tot][i]);//如果这个点的入度为0，则压入队列 
		} 
	} 
	for(int i=1;i<=n;++i){//寻找出度为0的点(最佳消费者) 
		if(outd[i]==0)//符合要求 
			ans=(ans+num[i])%mod;//累加答案 
	}
	cout<<ans;
	return 0;
}