P4017 最大食物链计数

题目背景

你知道食物链吗？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

说明/提示

各测试点满足以下约定：

【题解】

#include<bits/stdc++.h>
using namespace std;
const int N=6005,M=500005,mod=80112002;
#define ll long long
ll n,m,ft[N],nx[M],to[M],f[N],rd[N],ans;//rd[i]为i点的前驱数量,顺便记录一下一个点的所有前驱是否都走向它过
bool st[N];//因为前面rd有两个作用,所以需要这个来判断一个点是不是一开始就无前驱(具体的看下面)
inline long long read()
{
    char c=getchar();long long sum=0,f=1;
    while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {sum=((sum<<1)+(sum<<3))+(c-'0');c=getchar();}
    return sum*f;
}
void dfs(ll x)
{
    if(!rd[x])//如果所有的前驱都走到过它了,继续搜
    {
       if(!ft[x])//如果发现他不能继续走,即为终点
       {
           ans=(ans%mod+f[x]%mod)%mod;//记录
           return;//返回
       }
       else for(ll i=ft[x];i;i=nx[i])
       {
           rd[to[i]]--;//所到点的rd--
           f[to[i]]=(f[to[i]]%mod+f[x]%mod)%mod;//因为这种方法,每次到一个点是唯一的,所有直接用f[to[i]]+=f[x]并不会出现重复(刷表法)
           dfs(to[i]);///继续搜
       }
    }
    return;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        ll a=read(),b=read();
        rd[b]++;//前驱加一
        nx[i]=ft[a];//存路
        ft[a]=i;
        to[i]=b;
    }
    for(int i=1;i<=n;i++) if(!rd[i]) st[i]=1;//如果无前驱,为1
    for(int i=1;i<=n;i++) if(st[i]) f[i]=1,dfs(i);//因为搜索时会使rd[i]减为0来说明它已经被所有的前驱走到过了,所以如果这里再通过rd[i]==0来判断就会出现错误,所以要通过st来判断是原生态的无前驱节点
    cout<<ans%mod;//输出
    return 0;
}