题解

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 80112002;
const int N = 5010;

int n, m;
vector<int> g[N];
int in_deg[N], out_deg[N];
int dp[N];
void topo_sort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_deg[i] == 0) {
dp[i] = 1;
q.push(i);
}
}
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = 0;i < g[f].size();i++){
int now = g[f][i];
dp[now] = (dp[f] + dp[now]) % MOD;
in_deg[now]--;
if (in_deg[now] == 0){
q.push(now);
}
}
}
}

signed main() {

cin >> n >> m;
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    out_deg[u]++;
    in_deg[v]++;
}
topo_sort();
int ans = 0;
for (int i = 1;i <= n;i++){
    if (out_deg[i] == 0){
        ans = (ans + dp[i]) % MOD;
    }
}
cout << ans;

return 0;

}