题目

最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

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

接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

样例 #1

样例输入 #1

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

样例输出 #1

5

提示

各测试点满足以下约定：

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE ）

#include <iostream>
//#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>
#include <utility>
#include <unordered_map>
//#define x first
//#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
#define endl '\n'
#define buff ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
typedef unsigned long long ULL;
//int dx[] = { -1,-1,-1,0,0,1,1,1 };
//int dy[] = { -1,0,1,-1,1,-1,0,1 };
//#define INF 0x3f3f3f3f
//ceil函数可以把x上取整。
//floor函数可以把x下取整。
//round函数可以把x四舍五入。
//数字分为整型与浮点型，则对应的函数是stoi（）、stod（）、stof（）等。
//unordered_map<long, long> mp;
const int N = 5e3+2,mod = 80112002;
vector<int> e[N];//e[n]是箭头尾部指向的元素
int din[N],chu[N];//记录每一个点的入度,出度
int n, m;
int num[N];//记录每一个点有多少条路径可以到达
queue<int> q;
int ans;
void solve()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        din[b]++;//入度
        chu[a]++;//出度
    }
    for (int i = 1; i <= n; i++)
    {
        if (din[i] == 0)
        {
            num[i] = 1;
            q.push(i);
        }
    }
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (auto x : e[t])
        {
            if (--din[x] == 0) q.push(x);
            num[x] = (num[x] + num[t]) % mod; //加上之前的
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (chu[i] == 0)//出度为零就是最右边的
        {
            ans = (ans + num[i]) % mod;
        }
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}