3042: 【普及/提高-】【P4017】最大食物链计数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 秒的时间。
由于这个结果可能过大，你只需要输出总数模上 的结果。
输入
第一行，两个正整数 ，表示生物种类 和吃与被吃的关系数 。
接下来 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出
一行一个整数，为最大食物链数量模上 的结果。
样例输入 复制
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4样例输出 复制
5提示
各测试点满足以下约定：
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
#define MAXM 500005
#define MOD 80112002
int n,m,ans;
vector <int> p[MAXN];
queue <int> q;
int f[MAXN], ind[MAXN], outd[MAXN];
int main(){
cin >> n >> m;
for (int i = 1; i <=m; i++) {
int x, y;
cin >> x >> y;
outd[x]++; //点x的出度增加1
ind[y]++; //点y的入度增加1
p[x].push_back(y); //用邻接表记录下食物链的关系
}
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
if (ind[i] == 0) {
q.push(i); //将入度为0的点加入队列
f[i] = 1;
}
while (!q.empty()) {
int x=q.front();
q.pop();
for (int i = 0, sz = p[x].size(); i < sz; i++) {
int y = p[x][i];
f[y] = (f[x]+f[y]) % MOD;
ind[y]--;
if (ind[y] == 0) //此时点y已经没有入度了，将点y加入队列
q.push(y);
}
}
for (int i = 1; i <= n; i++)
if (outd[i] == 0) ans = (ans + f[i]) % MOD; //在出度为0的点中统计答案
cout << ans <<'\n';
return 0;
}