现在给你 n 个物种和 m 条能量流动关系，求其中的食物链条数。
物种的名称为从 1 到 n 编号，m 条能量流动关系形如
a1 b1
a2 b2
a3 b3
……
am−1 bm−1
am bm
其中 ai bi 表示能量从物种 ai 流向物种 bi，即 ai 和 bi 之间存在捕食关系，且 ai 是被捕食者， bi 是捕食者。一条食物链是从顶到底的，即从能量流向的起点到终点。如图中的草－＞兔－＞狐就是一条食物链，而草－＞兔则不是。
一条食物链至少包含两种生物。
输入描述
多组输入，每组第一行两个正整数 n 和 m。0 < n, m <= 1000
接下来 m 行每行两个整数 ai bi 表示 m 个捕食关系。
(数据保证输入数据符号合生物学特点，且不会有重复的能量流动关系出现)
输出描述
一个整数即食物网中的最长的食物链包含的生物数。
样例输入
Copy to Clipboard
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 8
7 6
7 9
8 5
9 8
10 6
10 7
10 9
样例输出
Copy to Clipboard
6
样例解释
输入的图就是上面题目描述的那个图。
各个物种的编号依次为：
草 <->1 兔 <->2 狐 <->3 鼠 <->4 猫头鹰 <->5 吃虫的鸟 <->6 蜘蛛 <->7 蛇 <->8 青蛙 <->9 食草昆虫 <->10。
最长的食物链为：1->10->7->6->8->5。
#include<bits/stdc++.h>
using namespace std;
int link[1000][1000];
bool vis[1000];
int dis[1000]={1};
int dfs(int i,int n)
{
if(vis[i]==1)
return dis[i];
int count=0;
for(int j=1;j<=n;j++)
{
if(link[i][j]==1)
{
count++;
}
}
if(count==0)
{
return dis[i];
}
for(int j=1;j<=n;j++)
{
if(link[i][j]==1)
{
dis[i]=max(dfs(j,n)+1,dis[i]);
}
}
vis[i]=1;
return dis[i];
}
int main()
{
int m,n;
while(cin>>n>>m)
{
int max=0,a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
link[a][b]=1;
}
for(int i=1;i<=n;i++)
{
if(max<dfs(i,n))
max=dfs(i,n);
}
cout<<max+1<<endl;
}
}
int link[1000][1000];这么大空间，申请不到吧
bool vis[1000]; 数组没有初始化