洛谷 P3183 [HAOI2016]食物链（dfs+记忆化搜索）

https://www.luogu.com.cn/problem/P3183

题目大意：

给定n个节点，标号分别为1——n，然后给出m条有向边，问我们不同的食物链路径有多少？

输入 #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

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
LL n,m;
LL mp[N];
vector<LL> g[N];
bool st[N];
int dfs(int idx)
{
    if(g[idx].size()==0) return 1;//它自己是最小的，返回当前这一个的数量
    if(mp[idx]) return mp[idx];//已经被标记过的了，直接返回
    int res=0;
    for(int i=0;i<g[idx].size();i++)
    {
        res+=dfs(g[idx][i]);//祖先辈中不同的数字下就有多少中不同的情况
    }
    return mp[idx]=res;//当前数量
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            LL u,v;
            cin>>u>>v;
            g[v].push_back(u);//装的是自己的上级
            st[u]=true;//如果不是食物链底端，则为true
        }
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            //从低到高寻找
            //是食物链的低端并且头上有人
            if(!st[i]&&g[i].size()) ans+=dfs(i);
        }
        cout<<ans<<endl;
    }
    return 0;
}

原文地址：http://www.cnblogs.com/Vivian-0918/p/16848620.html