洛谷P4017 最大食物链计数

(Large extbf{Description: } large{求最大食物链，n个点，m条边。(n leq 5000, m leq 500000)})

(Large extbf{Solution: } large{水题一道，直接拓扑排序。主要是想熟悉一下，以后生物考试可能用得到。})

(Large extbf{Code: })

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e3 + 5;
const int M = 5e5 + 6;
const int p = 80112002;
int n, m, cnt, in[N], out[N], head[N];
LL f[N];

struct Edge {
	int to, next;	
}e[M];
queue<int> q;

inline int read() {
	int ans = 0;
	char ch = getchar();
	while (ch > '9' || ch < '0') ch = getchar();
	while (ch >= '0' && ch <= '9') ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	return ans; 
}

inline void add(int x, int y) {
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}

int main() {
	n = read(), m = read();
	int x, y;
	for (int i = 1; i <= m; ++i) x = read(), y = read(), ++out[y], ++in[x], add(y, x);
	for (int i = 1; i <= n; ++i) if (!in[i]) q.push(i), f[i] = 1;
	while (!q.empty()) {
		int top = q.front(); q.pop();
		for (int i = head[top]; i ; i = e[i].next) {
			int u = e[i].to;
			f[u] = (f[u] + f[top]) % p;
			--in[u];
			if (!in[u]) q.push(u);
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i) if (!in[i] && !out[i]) ans = (ans + f[i]) % p;
	printf("%d
", ans);
	return 0;
}