【第71题】说好的练习动态规划，结果确是拓扑排序，最大食物链计数

5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

5

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <stack>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
#define endl '\n';

struct edge {
    int in_degree, out_degree;
};

bool cmp (edge x, edge y){
    return x.in_degree <= y.in_degree;
};
const int mod = 80112002;
void best_coder() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<edge> v(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[b].push_back(a);
        ++v[b].out_degree;
        ++v[a].in_degree;
    }
    queue<int> q;
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (v[i].in_degree == 0) {
            q.push(i);
            ans[i] = 1;
        }
    }

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        for (auto i : g[k]) {
            --v[i].in_degree;
            ans[i] = (ans[k] + ans[i]) % mod;
            if (v[i].in_degree == 0) {
                q.push(i);
            }
        }
    }
    long long cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (v[i].out_degree == 0) {
            cnt = (cnt + ans[i]) % mod;
        }
    }
    cout << cnt;

}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}