食物链计数-拓扑排序

食物链计数

题目描述

给你一个食物网，你要求出这个食物网中所有食物链的数量。（这里的“食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

由于这个结果可能过大，你只需要输出总数模上 10^8+7 的结果。

---

输入

第一行，两个正整数 n,m。表示生物种类 n 和吃与被吃的关系数 m。

接下来 m 行，每行两个正整数 A,B。表示生物 B 吃生物 A。保证不会出现环。

输出

一行一个整数，为最大食物链数量模上 10^8+7 的结果。

---

样例输入

7 9
1 3
1 4
2 3
2 4
2 5
3 6
4 6
4 7
5 7

样例输出

7

---

数据规模与约定

时间限制：1 s

内存限制：256 M

100% 的数据保证 1≤n≤5000,1≤m≤500000

思路

• 画个图就知道，该图是多颗树连接的图，想要统计食物链数量，只需要统计到根节点到叶子节点的路径数量
• 对于根节点，我们初始化其路径数量为1，利用拓扑排序把根节点去更新其他节点，直到叶子节点

代码演示

#include <stdio.h>

inline int read() {
    int x = 0, w = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}

#define MAX_N 5003
#define MAX_M 500005

const int mod = 1e8 + 7;

int n, m;
int rudu[MAX_N], chudu[MAX_N];
int cnt_edge, head[MAX_N], to[MAX_M], next[MAX_M];

inline void add_edge(int a, int b) {
    ++rudu[b];
    ++chudu[a];
    to[++cnt_edge] = b;
    next[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}

int q[MAX_M], l, r;

int cnt[MAX_N], ans;

inline void Topological_sorting() { //拓扑排序 
    while (l < r) {
        int tp = q[l++];
        for (int i = head[tp]; i; i = next[i]) {
            cnt[to[i]] += cnt[tp];
            cnt[to[i]] %= mod;
            if (--rudu[to[i]] == 0) {
                q[r++] = to[i];
            }
        }
    }
    return ;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a, b;
        a = read(), b = read();
        add_edge(a, b);
    }
    for (int i = 1; i <= n; i++) {
        if (rudu[i] == 0) { //入度为0的生物为生产者 
            cnt[i] = 1; // 初始化生产者为一条食物链 
            q[r++] = i;
        }
    }
    Topological_sorting();
    // 只需统计到达最顶端捕食者的食物链数量之和，即为答案 
    for (int i = 1; i <= n; i++) { //出度为0的生物为最顶端捕食者 
        if (chudu[i] == 0) ans += cnt[i];
    }
    printf("%d\n", ans);
    return 0;
}