一、题目描述：

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

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

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

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

来源：洛谷 www.luogu.com.cn/problem/P40…

输入格式

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

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

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

输出格式

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

5

二、思路分析：

我们在做这题之前需要搞清楚这个题目的规则，查看一共有多少条完整的食物链，而这个食物网中的顶层生物可能不止一个（即没有天敌的生物） 我们需要看食物链顶层的生物有多少种吃法，顶层的生物需要加上它吃的生物有多少种吃法......像一颗树一样。 换个说法就是我们要计算每个生物有多少种吃法，从底层叠加，这样就能推断出顶层的生物有多少种吃法了。

拓扑排序 是在不破坏节点先后顺序的前提下，找出所有的排序顺序， 如果最后不存在入度为0的节点,那就说明有环。找入度为0的结点加入排序列表（即没有可以吃的生物了的生物），把这个入度为0的结点加入列表后，将这个结点擦除，查看下一个入度为0的结点......以此类推

这里使用 beieat[] 记录每个生物 被吃的次数（出度），如果是0的话，就是食物链的最高级啦 eat[] 记录每个生物可以吃的下级生物个数（入度），方便我们进行排序， 如果是0的话，就是食物链的最底层啦

拓扑排序每次都把入度为0的数加入排序列表，我们的食物链每次把擦除生物结点后食物链的最底层加入排序列表

三、AC 代码：

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

public class Main {

	public static void main(String[] args) throws IOException {
           // 输入流
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
           // 生物种类 n 和吃与被吃的关系数 m
		String[] s = in.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
                
		int[] beieat = new int[n + 1];
		int[] eat = new int[n + 1];
                
           // 到这个生物为止往下有多少条不同的食物链
		int[] f = new int[n + 1]; 
		List<Integer>[] list = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++)
			list[i] = new LinkedList<>(); // 占位

		for (int i = 0; i < m; i++) {
			s = in.readLine().split(" ");
                // 被吃的生物A和吃A的生物B
			int A = Integer.parseInt(s[0]);
			int B = Integer.parseInt(s[1]); 
			beieat[A]++;
			eat[B]++;
                // 把吃与被吃的关系同列表储存
			list[A].add(B);
		}

		Queue<Integer> r = new LinkedList<>();
		for (int i = 1; i <= n; i++)
			if (eat[i] == 0) // 食物链的最底层，没有吃过其他生物
			{
				r.add(i);
				f[i] = 1;
			}
		while (!r.isEmpty()) {
			int x = r.poll();
                // 遍历所有可以直接吃 x 的生物
			for (int i = 0; i < list[x].size(); i++) {
				int k = list[x].get(i); 
                      // 取消k与x的关系路线
				eat[k]--;
                      // 加上所有它能吃掉的生物下面的条数
				f[k] = (f[k] + f[x]) % 80112002; 
                     //  它已变成食物链的最底层 敲重点！！！只有食物链底层才要入队
				if (eat[k] == 0) 
					r.add(k);
			}
		}

		int sum = 0;
		for (int i = 1; i <= n; i++) {
                // i作为食物链最高层时，有几条食物链
			if (beieat[i] == 0) 
				sum = (sum + f[i]) % 80112002;
		}
		System.out.println(sum);
	}
}

四、总结：

关于这个例子的答案应该是:

1 -> 2 -> 3 -> 4 -> 5

1 -> 2 -> 3 -> 5

1 -> 2 -> 5

1 -> 3 -> 4 -> 5

1 -> 3 -> 5