Description
通俗一点就是在一张图上求入度为0的点到出度为0的点路径的个数。
Solution
简要题意后发现可以拓扑排序？这里主要介绍记忆化搜索。
记忆化搜索是指记住当前节点的状态，待下次搜到这里直接调用即可，无需继续搜索。
显然由记忆化搜索延伸到dp，但如果状态设计很复杂记忆化搜索即可。
存图的时候记录一下每个点的入度和出度，dfs时如果该点出度为0，则代表一条食物链，返回1即可。
最后求答案时只需要找入度为0但是出度不为0的点开始dfs即可（单独的一个点不算）
具体实现见代码：
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 10010
using namespace std;
int dp[N];
int n,m;
int mapp[N][N];
vector <int> Edge[N];
int rem[N];
int ans = 0;
int in[N],out[N];
int dfs(int x)
{
if(rem[x]) return rem[x]; //记忆化
int sum = 0;
if(out[x] ==0 ) return 1; //如果出度为0则代表顶级消费者返回1即可
for(int i=0;i<Edge[x].size();i++)
{
sum += dfs(Edge[x][i]); //计算该节点食物链个数
}
rem[x] = sum; //记忆化
return sum; //记忆化后返回该节点食物链个数
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Edge[x].push_back(y);
in[y] ++; //记录入度出度
out[x] ++;
}
for(int i=1;i<=n;i++)
{
if((in[i]==0&&out[i]!=0)) //如果入度为0但是出度不为0则代表生产者开始dfs
ans += dfs(i);
}
cout<<ans<<endl;
return 0;
}