思路

记忆化搜索、拓扑排序的题目。
对于一个已经走过一次的点，后面能走的情况都是确定的，
只要能把情况数记录下来，后面的结点就不需要再走一遍了，
就可以很大程度上节省时间。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxm=200005,maxn=100005;

struct E{
    int next, to;
}edge[maxm];

int head[maxn], cnt, ans;
int n,m,a,b,ru[maxn],chu[maxn],f[maxn];

void addedge(int a,int b){
    edge[++cnt].next=head[a];
    edge[cnt].to=b;
    head[a]=cnt;
}

int dfs(int now){
    if(f[now]) return f[now]; //记忆化 
    if(!chu[now]) return 1;
    int res=0;
    for(int i=head[now];i;i=edge[i].next){
        res+=dfs(edge[i].to);
    }
    f[now]=res;
    return res;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    memset(ru, 0, sizeof(ru));
    memset(chu, 0, sizeof(chu));
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        addedge(a,b);
        ru[b]++,chu[a]++;
    }
    for(int i=1;i<=n;i++){
        if(!ru[i]&&chu[i]) ans+=dfs(i);
    }
    cout<<ans;
    return 0;
}