题解 | 食物链计数

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
//倒序不要忘记是--不是++
void solve(){
    int n,m;cin>>n>>m;
    vector<vector<int>> e(n+1);
    vector<int> deg(n+1),chu(n+1);
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        deg[v]++;
        chu[u]++;
    }
    vector<int> dp(n+1);
    auto dfs=[&](auto dfs,int u)->int{
        if(dp[u]) return dp[u]; 
        if(e[u].size()==0){
            return dp[u]=1;
        }
        for(auto i:e[u]){
            dp[u]+=dfs(dfs,i);
        }
        return dp[u];
    };
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!deg[i]&&!chu[i]) continue;
        if(!deg[i]){
            ans=(ans+dfs(dfs,i));
        }
    }
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}