食物链计数

题目描述
​ 给你一个食物网，你要求出这个食物网中所有食物链的数量。（这里的“食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

​ 由于这个结果可能过大，你只需要输出总数模上 108+7 的结果。

输入
​ 第一行，两个正整数 n,m。表示生物种类 n 和吃与被吃的关系数 m。

​ 接下来 m 行，每行两个正整数 A,B。表示生物 B 吃生物 A。保证不会出现环。

输出
​ 一行一个整数，为最大食物链数量模上 108+7 的结果。

样例输入
7 9
1 3
1 4
2 3
2 4
2 5
3 6
4 6
4 7
5 7
样例输出
7
数据规模与约定
​ 时间限制：1 s

​ 内存限制：256 M

​ 100% 的数据保证 1≤n≤5000,1≤m≤500000

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct edge {
	int to, next;
};

int n, m,head[5005],in_degree[5005],out_degree[5005],ans[5005];
queue<int> que;
edge edg[500005];

int main() {
	memset(head, -1, sizeof(head));
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edg[i].to = b;
		edg[i].next = head[a];
		head[a] = i;
		in_degree[b]++;
		out_degree[a]++;
	}
	for (int i = 1; i <= n; i++) {
		if (in_degree[i] == 0) {
			que.push(i);
			ans[i] = 1;
		}
	}
	while (!que.empty()) {
		int t = que.front();
		que.pop();
		for (int i = head[t]; i != -1; i = edg[i].next) {
			int e = edg[i].to;
			ans[e] += ans[t];
			ans[e] %= 100000007;
			in_degree[e]--;
			if (in_degree[e] == 0) {
				que.push(e);
			}
		}
	}
	int fin = 0;
	for (int i = 1; i <= n; i++) {
		if (out_degree[i] == 0) {
			fin += ans[i];
			fin %= 100000007;
		}
	}
	cout << fin << endl;
	return 0;
}