原文地址：http://www.cnblogs.com/GXZlegend/p/6832118.html
题目描述
如图所示为某生态系统的食物网示意图，据图回答第1小题
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
......
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
输入
第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。
（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）
1<=N<=100000 0<=m<=200000
题目保证答案不会爆 int
输出
一个整数即食物网中的食物链条数
样例输入
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
题目大意
给定你一个DAG图，求任意一条从入度为0的点到出度为0的点的方案数，其中不包括入度和出度都为0的点
题解
拓扑排序+dp，难在题意
设f[i]表示从某个入度为0的点到点i的方案数，然后按照类似拓扑排序的方法，由入度为0的点更新其它点。
注意一下入度和出度都为0的点要特判一下。
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100010
using namespace std;
queue<int> q;
int head[N] , to[N << 1] , next[N << 1] , cnt , rd[N] , cd[N] , f[N];
void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
int main()
{
int n , m , i , x , y , ans = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , cd[x] ++ , rd[y] ++ ;
for(i = 1 ; i <= n ; i ++ )
{
if(!rd[i])
{
if(cd[i]) f[i] = 1;
q.push(i);
}
}
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
f[to[i]] += f[x] , rd[to[i]] -- ;
if(!rd[to[i]]) q.push(to[i]);
}
}
for(i = 1 ; i <= n ; i ++ ) if(!cd[i]) ans += f[i];
printf("%d
" , ans);
return 0;
}