# 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
```

拿到这道题，我的想法是构造图之后获得每个入度为0的点到出度为0且入度不为0的点的路径之和，在数据量小的情况下似乎是可以运行的，但是数据量大超时了，原因在于暴力搜索会因为多次访问同一节点而效率低下，特别是当出度或入度较高时，递归深度和重复计算急剧增加，在观看了几篇题解后，发现该题可以用拓扑排序解决，使用了拓扑排序，使得这道题的运行达到了线性，时间复杂度为O(n+m)

为什么使用拓扑排序

那么为什么可以使用拓扑排序，是因为我们在处理某个点的path的时候，已经把他的前驱都计算好了，在计算2时，1处理好了，他的结果是正确的，在计算3时，2处理好了，在计算4时，3处理好了，在计算5时，2，3，4处理好了，队列对于每个点的处理，都是建立在食物链的流动方向上的

原始dfs代码(我一开始的思路)

package luogu;

import java.util.Scanner;

public class A4017 {
    static int[] h;
    static int[] e;
    static int[] ne;
    static int idx=1;
    static int[] vis;
static int n;
static int m;
static int[] d;//入度
    static int[] up;//出度
    static int res=0;//食物链数
static void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
static void dfs(int a){
    if(up[a]==0){
        //该生物出度为0，是食物链终点，添加食物链,返回
        res++;
        return;
    }
    for(int edge=h[a];edge!=0;edge=ne[edge]){
        int end=e[edge];
        if(vis[end]==0){
            vis[end]=1;
            dfs(end);
            vis[end]=0;//恢复现场
        }
    }
}
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
h=new int[n+1];
vis=new int[n+1];
d=new int[n+1];
e=new int[m+10];
ne=new int[m+10];
up=new int[n+1];
int a,b;
for(int i=1;i<=m;i++){
    a=sc.nextInt();
    b=sc.nextInt();
    add(a,b);
    d[b]++;
    up[a]++;
}
for(int i=1;i<=n;i++){
    if(d[i]==0&&up[i]!=0)
        dfs(i);
}
        System.out.println(res%80112002);
    }
}

拓扑排序代码

package luogu;

import java.io.*;
import java.util.Scanner;

public class A4017P2 {
    static int[] h;
    static int[] e;
    static int[] ne;
    static int idx=1;
    static int[] vis;
    static int n;
    static int m;
    static int[] d;//入度
    static int[] up;//出度
    static int res=0;//食物链数
    static int[] path;
    static final int MOD= 80112002;
    static final int N=500050;
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static void topo(){
        int[] q=new int[n+10];
        int hh=0,tt=-1;
        //将入度为0的点加入队列
        for(int i=1;i<=n;i++){
            if(d[i]==0){
                path[i]=1;
                q[++tt]=i;
            }
        }
        while(hh<=tt){
            int head=q[hh++];
            //枚举该点的边
            for(int edge=h[head];edge!=0;edge=ne[edge]){
                int end=e[edge];
                path[end]=(path[head]+path[end])%MOD;
                d[end]--;//入度减1
                if(d[end]==0)q[++tt]=end;
            }
        }
        for(int i=1;i<=n;i++){
            if(up[i]==0)res+=path[i];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log=new BufferedWriter(new OutputStreamWriter(System.out));
        String[] params = br.readLine().split(" ");
        n = Integer.parseInt(params[0]);
        m = Integer.parseInt(params[1]);

        h=new int[n+5];
        vis=new int[n+5];
        d=new int[n+5];
        e=new int[N];
        ne=new int[N];
        up=new int[n+5];
        path=new int[n+5];
        for(int i=1; i<=m; i++){
            String[] edge = br.readLine().split(" ");
            int a = Integer.parseInt(edge[0]);
            int b = Integer.parseInt(edge[1]);
            add(a,b);
            d[b]++;
            up[a]++;
        }
      topo();
        log.write(Integer.toString(res%MOD));
        log.flush();

    }
}