暴力递归

用存储图的方式记录下捕食者的数组，然后再从最底端食物链往上面遍历，每遇到没有捕食者的编号时，就说明已经到达食物链的顶端，此时放回 1

接下来我们要统计有多少个 1 就行

假设函数 dfs 可以放回从当前节点到达食物链顶端的个数去求解

#include<bits/stdc++.h>

using namespace std;

// 即使是不成熟的尝试，

const int N = int (1e6 + 10);

int mod = 80112002;
int n, m, a, b, res;
int hunts[N], e[N], ne[N], cnt, q[N];

void add(int a, int b) {
    e[++cnt] = b;
    ne[cnt] = hunts[a];
    hunts[a] = cnt;
    q[b] = 1;
}

int dfs(int idx) {
    if (hunts[idx] == 0) return 1;
    int sum = 0, i = hunts[idx];
    while (i) {
        sum = (sum + dfs(e[i])) % mod;
        i = ne[i];
    }
    return sum;
}

void solve(void) {
    cin >> n >> m;
    while (m --) {
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i ++) {
        if (q[i] == 0) res = (res + dfs(i)) % mod;
    }
    cout << res << endl;
}

// 也胜于胎死腹中的策略。

int main(void) {
    ifstream fin("../LinRQ.in");
    ofstream fout("../LinRQ.out");
    if (fin.is_open() && fout.is_open()) {
        cin.rdbuf(fin.rdbuf());
        cout.rdbuf(fout.rdbuf());
    }
    else {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    solve();

    return 0;
}

自顶向下的记忆化递归

#include<bits/stdc++.h>

using namespace std;

// 即使是不成熟的尝试，

const int N = int (1e6 + 10);

int mod = 80112002;
int n, m, a, b, res;
int hunts[N], e[N], ne[N], cnt, q[N];
int dp[N];

void add(int a, int b) {
    e[++cnt] = b;
    ne[cnt] = hunts[a];
    hunts[a] = cnt;
    q[b] = 1;
}

int dfs(int idx) {
    if (dp[idx]) return dp[idx];
    if (hunts[idx] == 0) return dp[idx] = 1;
    int sum = 0, i = hunts[idx];
    while (i) {
        sum = (sum + dfs(e[i])) % mod;
        i = ne[i];
    }
    return dp[idx] = sum;
}

void solve(void) {
    cin >> n >> m;
    while (m --) {
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i ++) {
        if (q[i] == 0) res = (res + dfs(i)) % mod;
    }
    cout << res << endl;
}

// 也胜于胎死腹中的策略。

int main(void) {
    ifstream fin("../LinRQ.in");
    ofstream fout("../LinRQ.out");
    if (fin.is_open() && fout.is_open()) {
        cin.rdbuf(fin.rdbuf());
        cout.rdbuf(fout.rdbuf());
    }
    else {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    solve();

    return 0;
}

自底向上的动态规划

递归的底部

递归的底部是编号 idx 没有捕食者的动物，也代表食物链的最顶端

底部的上一层是底部 idx 的食物 fd[idx] 但该食物的入度为 1，即他的捕食者都应该是已知的

出度为 0 的，是食物链最底部的生产者 入度为 0 的，是食物链最顶端的最高级消费者

每求出一个 idx 的 dp 值，就要把 idx 的食物入度 -1

如果 idx 的入度是 0，说明我们可以通过已知的推导出 idx 的 dp 值，如果不是 0，就滞留，稍后再处理

上下层的联系

上层动物的捕食者可以组成一个集合 S，则该动物的食物链数就是该捕食者构成的集合的链数之和

代码实现

#include<bits/stdc++.h>

using namespace std;

// 即使是不成熟的尝试，

const int N = int (1e6 + 10);

int mod = 80112002;
int n, m, a, b, res;

// ht[i] 是i的捕食者构成的链，fd[i] 是i的食物构成的链
// ot[i] 是 i 的出度，in[i] 是 i 的入度
int ht[N], fd[N], ot[N], in[N];
int e[N], ne[N], cnt, dp[N];

// a 是被捕食者，b 是捕食者
void add(int a, int b) {
    e[++cnt] = a; ne[cnt] = fd[b]; fd[b] = cnt;
    e[++cnt] = b; ne[cnt] = ht[a]; ht[a] = cnt;
    in[a] ++; ot[b] ++;
}

void solve(void) {
    cin >> n >> m;
    while (m --) {
        cin >> a >> b;
        add(a, b);
    }
    queue<int> qu;
    for (int i = 1; i <= n; i ++) {
        if (in[i] == 0) {
            qu.push(i);
        }
    }
    while (qu.size()) {
        int node = qu.front(); qu.pop();
        if (in[node] == 0) {
            if (dp[node] == 0) {
                int idx = ht[node];
                if (idx == 0) dp[node] = 1;
                while (idx) {
                    int i = e[idx]; idx = ne[idx];
                    dp[node] = (dp[node] + dp[i]) % mod;
                }
                idx = fd[node];
                while (idx) {
                    int i = e[idx]; idx = ne[idx];
                    in[i] --; qu.push(i);
                }
            }
        }
        else {
            qu.push(node); continue;
        }
    }
    for (int i = 1; i <= n; i ++) {
        if (ot[i] == 0) res = (res + dp[i]) % mod;
    }
    cout << res << endl;
}

// 也胜于胎死腹中的策略。

int main(void) {
    ifstream fin("../LinRQ.in");
    ofstream fout("../LinRQ.out");
    if (fin.is_open() && fout.is_open()) {
        cin.rdbuf(fin.rdbuf());
        cout.rdbuf(fout.rdbuf());
    }
    else {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    solve();

    return 0;
}