题目：https://www.luogu.com.cn/problem/P3183

一道记忆化搜索的题。

大意是给出一个食物链，求食物链的条数。

很明显我们可以用dfs来解这个题，从入度为0的点开始，dfs去找，找到出度为0的点算是一条食物链。   用sign记录改点是否被访问，然后进行回溯。
但是这个题针对爆搜来说并不能过所有测试点。

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
vector<int> food[nn];
bool sign[nn];
int ans = 0;
bool is_food[nn];
void dfs(int x)
{
	if(food[x].size()==0)
	{
		ans++;
		return;
	}
	for(int i=0;i<food[x].size();i++)
	{
		if(!sign[food[x][i]])
		{
			sign[food[x][i]]=true;
			dfs(food[x][i]);
			sign[food[x][i]]=false;
		}
	}
}
int main()
{
	memset(is_food,false,sizeof is_food);
	int n,m,x,y;
	cin>>n>>m;
	while(m--){
		scanf("%d%d",&x,&y);
		is_food[y] = true;
		food[x].push_back(y); 
	}
	for(int i=1;i<=n;i++)
	{
		memset(sign,false,sizeof sign);
		sign[i] = true;
		if(food[i].size()>0&&!is_food[i])
			dfs(i); 
	}
	cout<<ans<<endl;
} 

那么就需要记忆化搜索来做。用临时sum记录该点通过的所有点的可行食物链。对食物进行dfs，这样每一个点能够能通过的食物链的数量就出来了。i
f(eat[x]) return eat[x];为记忆化搜索语句，当我们得出sum记录的该点通过的可行食物链的数量之后记录到记忆化中。eat[x] = sum;

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
vector<int> food[nn];
bool is_food[nn];
int eat[nn];
int ans = 0;
int dfs(int x)
{
	if(eat[x])	return eat[x];
	int sum = 0;
	if(food[x].size()==0)	return 1;
	for(int i=0;i<food[x].size();i++)
	{
		sum+=dfs(food[x][i]);
	}
	eat[x] = sum;
	return sum;
}
int main()
{
	memset(is_food,false,sizeof is_food);
	int n,m,x,y;
	cin>>n>>m;
	while(m--){
		scanf("%d%d",&x,&y);
		is_food[y] = true;
		food[x].push_back(y); 
	}
	for(int i=1;i<=n;i++)
	{
		if(food[i].size()>0&&!is_food[i])
			ans+=dfs(i); 
	}
	cout<<ans<<endl;
}