P4017 最大食物链计数-526互联

\(P4017\) 最大食物链计数

最大食物链数量；最大指的是需要从一个入度为零的点开始到一个出度为零的点,这是一个完整的食物链，问我们给出的食物网中，食物链的数量
① 本题中，不仅需要 记录一下入度 , 还要 记录一下出度，这是因为我们要计算食物链的数量，食物链的最后一个结点，就是出度为零的点
② 食物链的数量,就是一个类似于　数字三角形　求值的\(dp\)问题了

#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;
}

食物链