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;
}