洛谷P4017 最大食物链计数

拓扑排序板子题

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

//Mystery_Sky

//

#define maxn 1000010

#define maxm 5000050

#define mod 80112002

struct Road{

    int next;

    int to;

};

Road road[maxn];

int head[maxm], cnt;

inline void add_edge(int u, int v) {

    road[++cnt].to = v;

    road[cnt].next = head[u];

    head[u] = cnt;

}

int ind[maxn], eat[maxn];

int d[maxn];

int n, m;

queue <int> q;

inline void topo() {

    for(int i = ; i <= n; i++) {

        if(!ind[i]) {

            q.push(i);

            d[i]++;

        }

    }

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        for(int i = head[now]; i; i = road[i].next) {

            int e = road[i].to;

            d[e] = (d[e] + d[now]) % mod;

            if(! --ind[e]) q.push(e);

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        add_edge(a, b);

        ind[b]++;

        eat[a]++;

    }

    topo();

    int ans = ;

    for(int i = ; i <= n; i++) {

        if(!eat[i]) ans = (ans + d[i]) % mod;

    }

    printf("%d\n", ans);

    return ;

}