题目来源：洛谷
题目描述
如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
输入输出格式
输入格式：
第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1<=N<=100000 0<=m<=200000题目保证答案不会爆 int
输出格式：
一个整数即食物网中的食物链条数
输入输出样例
输入样例#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
输出样例#1：
9 解析：
这题还可以dp，比较水。
我写的是裸的拓扑排序，不多说。
具体看代码。
注意：d[]储存的是经过某一点的食物链条数。而且，这道题有8个测试点都带有孤立节点，别问我是怎么知道的。 参考代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100010
#define MOD 2520
#define E 1e-12
using namespace std;
queue<int> q;
struct rec{
int next,ver;
}g[N<<];
int head[N],tot,n,m,ing[N],cnt,d[N];
bool v[N<<];
void add(int x,int y)
{
g[++tot].ver=y;
g[tot].next=head[x],head[x]=tot;
ing[y]++;//可以在此时就统计入度了
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
add(x,y);
}
for(int i=;i<=n;i++)
if(ing[i]==&&head[i]!=) q.push(i),d[i]=;//可以用head[]判断孤立点
while(q.size())//裸的拓扑
{
int x=q.front();q.pop();
if(head[x]==) cnt+=d[x];//依旧是骚的一批的head[]判断出边
for(int i=head[x];i;i=g[i].next)
{
int y=g[i].ver;
d[y]+=d[x];//累计经过该点的食物链条数
if(--ing[y]==) q.push(y);
}
}
cout<<cnt<<endl;
return ;
}