• de了很长时间，一直没懂后面6个点WA在哪里，求大佬解惑ww
• 使用的是DFS+记忆化搜索
• 感谢大佬！

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
using namespace std;

const int N=5020,Mod=80112002;

int n,m;
bool eater[N];//吃别人
bool grass[N];//被别人吃
int memory[N];

unordered_set<int> start;
unordered_set<int> target;
vector<int> g[N];

int dfs(int idx){
    if(target.count(idx)){
        return 1;
    }
    if(memory[idx]){
        return memory[idx];
    }
    int res=0;
    for(int i=0;i<g[idx].size();i++){
        res+=dfs(g[idx][i])%Mod;
    }
 //   cout << res << endl;
    memory[idx]=res%Mod;
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        grass[x]=true;
        eater[y]=true;
        g[x].push_back(y);
    }
    //init
    for(int i=1;i<=n;i++){
        if(grass[i] && !eater[i]) start.insert(i);
        if(!grass[i] && eater[i]) target.insert(i);
    }
    int res=0;
    for(int i=0;i<n;i++){
        if(start.count(i)){
            res+=dfs(i);
        }
    }
    printf("%d",res%Mod);
    return 0;
}