[JZOJ5166] [NOIP2017模拟6.26卢学魔] 解题报告 （记忆化搜索|拓扑排序）

题目链接：

http://172.16.0.132/senior/#main/show/5166

题目：

题解：

这个没什么好讲的，就是注意生产者没人吃也不是食物链，这告诉我们要积累生物知识注意细节

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;

const int N=1e5+15;
int n,m,tot;
int ru[N],head[N],chu[N];
ll dp[N];
queue <int> q;
struct EDGE
{
    int to,nxt;
}edge[N<<1];
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
void add(int u,int v)
{
    edge[++tot]=(EDGE){v,head[u]};
    head[u]=tot;
}
int dfs(int x)
{
    if (!chu[x]) 
    {
        dp[x]=1;return dp[x];
    }
    for (int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if (!dp[y]) dp[y]=dfs(y);
        dp[x]+=dp[y];
    }
    return dp[x];
}
int main()
{
    n=read();m=read();
    for (int i=1,u,v;i<=m;i++)
    {
        u=read();v=read();
        add(u,v);chu[u]++;ru[v]++;
    }
    for (int i=1;i<=n;i++) if (!dp[i]) dfs(i);
    ll ans=0;
    for (int i=1;i<=n;i++) if (!ru[i]&&head[i]) ans+=dp[i];//head[i]不可以去掉，生产者没人吃也不是食物链 
    printf("%lld
",ans);
    return 0;
}