P3183 [HAOI2016]食物链 如果求最长食物链所包含的生物数量的话 我用的dfs,但是一直wa,求各位大佬看看
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define maxm 1005
int out[maxn],in[maxn];
int u[maxm], v[maxm];
int f[1005];
struct Edge{
int nxt, to;
}e[maxm];
int head[maxn], cnt;
void addEdge(int u,int to)
{
e[++cnt].nxt=head[u];//上一条以u为起点的边
e[cnt].to=to;
head[u]=cnt;//标号,标记最后一次出现以u为起点的边
}
int dfs(int x)
{
int max_length=0;
if(f[x]>0)
return f[x];
if(out[x]==0)
{
f[x]=1;
return f[x];
}
//cout<<"running..."<<endl;
for(int i=head[x];i;i=e[i].nxt)
{
//cout<<max_length<<endl;
max_length=max(max_length,dfs(e[i].to));
}
f[x]=max_length+1;
//cout<<f[i]<<" "<<i<<endl;
return max_length+1;
}
int main()
{
int n,m;
while(cin>>n)
{
memset(f,0,sizeof(f));
memset(e,0,sizeof(e));
int ans=0;
cin>>m;
for (int i = 1; i <=m; i++)
{
cin>>u[i]>>v[i];
addEdge(u[i],v[i]);
out[u[i]]++;
in[v[i]]++;
}
for (int i = 1; i <=n; i++)
{
/* code */
if(in[i]==0&&out[i]!=0)
{
//cout<<i<<endl;
ans=max(ans,dfs(i));
}
}
// cout<<head[1]<<" "<<e[head[1]].to<<" "<<e[head[1]].nxt<<endl;
// cout<<f[1]<<f[2]<<f[3]<<f[4]<<endl;
// cout<<dfs(1)<<endl;
cout<<ans<<endl;
}
system("pause");
return 0;
}