最大食物链计数

原题链接：最大食物链计数

题意：

给你一个食物网，请求出这个食物网中最大食物链的数量。n代表物种的种类，m代表食物链有几条边，接下来m行，每行a，b代表被吃者a和捕食者b。

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

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

注：最大食物链，链的最左边和最右边的端点已经不能再扩展了，最左边的端点一定是食物链的最低层，最右边的端点一定是食物链的最高层。

所以想要找到一条 最大食物链，则起始点入度要为0，终点出度要为0。于是有既要记录入度，还要记录出度！ 以任一点结尾的最大食物链的数量，都取决于蓝色点，由下图可得： 所以通过拓扑排序将需要删除的点的价值都累加到它可以到达的点上面去，最后累加所有红色点（最佳消费者）的答案，输出即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

vector<int> arr[5005];
bool pd[5005];
ll dp[5005];
const int mod = 80112002;

ll dfs(const int &t){
	if (dp[t]) return dp[t] % mod;
	else dp[t] = 0;
	for (int i = 0; i < arr[t].size(); i++){
		dp[t] += dfs(arr[t][i]);
		dp[t] %= mod;
	}
	return dp[t];
}
int main()
{
	ios;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		arr[y].push_back(x);
		pd[x] = 1;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++){
		if (arr[i].size() == 0){
			dp[i] = 1ll;
		}
	}
	for (int i = 1; i <= n; i++){
		if (!pd[i]){
			ans += dfs(i);
			ans %= mod;
		}
	}
	cout << ans <<"\n";
    return 0;
}