食物链

提交数: 51, 通过率: 11.76%, 平均分: 19.8

题目描述:

给定一个生态系统,其中包括n个物种和m条捕食关系,求生态系统中的食物链条数。

如下图中共有9条食物链(你也许曾经生物课上手算过)。

1551706443720277655.png

补充说明:捕食食物链的起点是生产者,终点是不被其他动物所食的的动物,不出现非生物物质和能量及分解者,即只有生产者和消费者。

输入格式:

第一行为数据组数T。

接下来T组,开头两个整数n和m,接下来m行,每行两个整数u,v表示存在从u被v捕食。

其中T<=30, n<=100000, m<=200000, 1<=u,v<=n。

输出格式:

对于每一组数据,输出一个整数,表示食物链的条数,答案 mod 1e9+7。

样例输入:

1
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

样例输出:

9

提示:

样例即为上图,编号为草是1,其余从左到右依次编号。

如果实在没有思路的话,可以参考算法导论练习题22.4-2。

时间限制: 2000ms
空间限制: 128MB

来源: HAOI 2016 d1t1