P4017 最大食物链计数
初中生物都忘了，食物链不知道从生产者还是消费者开始了
题目给出有向无环图，从入度为零的点（不保证唯一）开始，走到出度为零的点（不保证唯一）共有多少条路径，答案对80112002取模
保证：
道路单向无重边（A吃B就没有B吃A，也不会自己吃自己）
图中无环 （不会有A吃B，B吃C，C吃A）
思路
一眼是dfs，但是时间复杂度 $ O（MN^2) $ 数据卡的太死了，只有20%
那么想快一点的方法：
用数组 \(lenth[i]\) 表示从任意一个入度为零的点到i点的链长度
对于任意一个入度为零的点\(x\)，\(f[x]\)初始化为1
对于任意入度非零的点y，\(f[y]\) 等于任意能到达\(y\)点的\(u\)点的\(f[u]\)之和
因此需要计算保证任意点链长时，所有可达该点的节点链长已经被计算
所以我们需要拓扑排序，找到一个合适的计算顺序保证上述条件
坑
- “最左端是不会捕食其它生物的生产者，最右端是不会被其他生物捕食的消费者”
并且（A，B）表示“被吃的生物A和吃A的生物B”
建图开个vector，存单向边应该从A到B （不是捕食关系，而是被捕食关系，初中生物全忘了
-
起点和终点不唯一，可能有多个起点和终点，入队的时候要都进去，计算总和的时候要计算所有出度为零的点的链长和
-
数据可能很大，计算过程中随时模mod，否则有可能爆
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int mod = 80112002, N = 5009;
int n, m, A, B, out[N], in[N], lenth[N], ans;
vector<int> v[N];
struct queue{ // 手写队列
int head = 0, tail = 0, que[N + 10];
void push(int x) {que[tail ++] = x;}
void pop() {head ++;}
int front() {return que[head];}
int size() {return tail - head;}
bool empty() {return head >= tail;}
void clear() {head = tail = 0;}
}q;
int main() {
// freopen("P4017_1.in", "r", stdin);
scanf("%d%d", &n, &m);
while (m --) {
cin >> A >> B;
v[A].push_back(B); // 建A向B的单向边
out[A] ++; // A的出度 ++
in[B] ++; // B的入度 ++
}
for (int i = 1; i <= n; i ++)
if (!in[i]) { // 循环找所有可能起点
q.push(i); // 入队
lenth[i] = 1; // 链长为1
}
while (!q.empty()) { // 拓扑排序
int head = q.front();
q.pop();
for (int i = 0; i < v[head].size(); i ++) {
int p = v[head][i];
in[p] --; // 相连的点入度 --
lenth[p] = (lenth[p] + lenth[head]) % mod; // 计算链长
if (in[p] == 0) q.push(p); // 将入度为零的点入队
}
}
for (int i = 1; i <= n; i ++)
if(!out[i]) ans = (ans + lenth[i]) % mod; // 随时模
// 统计所有可能的终点的链长和
printf("%d", ans % mod);
return 0;
}