python/TangDou/AcWing/TopSort/P4017.md

## [$P4017$ 最大食物链计数](https://www.luogu.com.cn/problem/P4017)

>**最大食物链数量**；最大指的是需要**从一个入度为零的点开始到一个出度为零的点**,这是一个完整的食物链，问我们给出的食物网中，**食物链的数量**
① 本题中，不仅需要 **记录一下入度** , 还要 **记录一下出度**，这是因为我们要计算食物链的数量，食物链的最后一个结点，就是出度为零的点
② 食物链的数量,就是一个类似于　**数字三角形**　求值的$dp$问题了
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 500010;
const int INF = 0x3f3f3f3f, MOD = 80112002;

int in[N], out[N], f[N];
int n, m;

//链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void topsort() {
    queue<int> q;

    for (int i = 1; i <= n; i++)
        if (!in[i]) {
            q.push(i);
            f[i] = 1;
        }

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            in[j]--;
            f[j] = (f[j] + f[u]) % MOD;
            if (in[j] == 0) q.push(j);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        in[b]++, out[a]++;
    }

    topsort();

    int res = 0;

    for (int i = 1; i <= n; i++)
        if (!out[i]) res = (res + f[i]) % MOD;

    printf("%d", res);
    return 0;
}
```