题目背景
你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。
题目描述
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 1 秒的时间。
由于这个结果可能过大，你只需要输出总
数模上 80112002 的结果。
输入格式
第一行，两个正整数 n,m，表示生物种类 n 和吃与被吃的关系数 m。
接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出格式
一行一个整数，为最大食物链数量模上 80112002 的结果。
样例 #1
样例输入 #1
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
样例输出 #1
5
提示
各测试点满足以下约定：
【补充说明】
数据中不会出现环，满足生物学的要求。（感谢 @AKEE ）
题目分析
它是一个 DAG ，并且画图发现，下一个点的答案可以从前一个点的答案转移而来。所以我们要找一种顺序，来合并这些答案。
于是可以想到拓扑排序，当该点的入度为 0 时，说明前面的点都被处理过，答案已经是最优了。
拓扑排序
对于图的拓扑排序，有一些细节。我们可以发现一张图不一定只有一个出发点，我称之为不严格拓扑排序（如果严格的话只有一种排法了，可以参考P1347排序），同样，它也有多个结束点。所以刚开始的时候要将所有入度为 0 的点都 push 进队列，在最后要统计所有出度为 0 的点的答案。
此外，我们还发现题目虽然说的是 x 被 y 吃，但是拓扑排序，把所有边都反一下是没有问题的，不过如果在上面那个细节中没有统计完全，那么读入顺序是有区别的（亲身经历）。
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MOD = 80112002;
int n, m;
const int N = 5010;
const int M = 5e5 + 10;
int dp[N];
struct edge{
int from, to;
};
vector<int> topusplit;
vector<int> G[N];
int indeg[N], outdeg[N];
inline void topu() {
queue<int> q;
for(int i = 1; i <= n; i++) {
if(indeg[i] == 0) {q.push(i); dp[i] = 1;}
}
while(!q.empty()) {
int now = q.front(); q.pop();
topusplit.emplace_back(now);
int sz = G[now].size();
for(int i = 0; i < sz; i++) {
int s = G[now][i];
indeg[s]--;
dp[s] += dp[now];
dp[s] %= MOD;
if(indeg[s] == 0) q.push(s);
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(outdeg[i] == 0) ans += dp[i], ans %= MOD;//跟开始一样，统计所有出度为0的点
}
printf("%d\n", ans);
}
int main()
{
// freopen("P4017_1.in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d%d", &n, &m);
int u, v;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
G[u].emplace_back(v);
indeg[v]++, outdeg[u]++;
}
for(int i = 1; i <= n; i++) {
dp[i] = 0;
}
topu();
return 0;
}
正文完
