题解 | #[HAOI2016]食物链#

学了两天的链式前向星知识，终于可以独立写出代码，想用链式前向星可以参考AC了

#include <bits/stdc++.h>
using namespace std;
const int maxN=100005;
const int maxM=200005;
int head[maxN];
int to[maxM];
int Next[maxM];
int cnt=1;
int inDeg[maxN];
int dp[maxN];
int dfs(int now,int level) {
    if (dp[now]!=-1) {
        return dp[now];
    }
    if (head[now]==0) {
        if (level==1) {
            return 0;
        }
        return 1;
    }
    int sum=0;
    for (int i=head[now];i>0;i=Next[i]) {
        sum+=dfs(to[i],level+1);
    }
    return dp[now]=sum;
}
void add(int u,int v) {
    Next[cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt++;
    inDeg[v]++;
}
int main() {
    int n,m;cin >> n >> m;
    memset(dp,-1,sizeof(dp));
    memset(inDeg,0,sizeof(inDeg));
    memset(Next,0,sizeof(Next));
    memset(to,0,sizeof(to));
    while(m--) {
        int u,v;cin >> u >> v;
        add(u,v);
    }
    int cnt=0;
    for(int i=1;i<=n;i++) {
        if(inDeg[i]==0) {
            cnt+=dfs(i,1);
        }
    }
    cout<<cnt<<endl;
}