http://www.lydsy.com/JudgeOnline/problem.php?id=4562 https://www.luogu.org/problem/show?pid=3183 可以搜索的题嘛。。。 首先找入度为零的点（生产者），从生产者开始向下寻找，直到找到出度为零的点（终极消费者）就算找到一条食物链（生物知识） 但是总不可能一条一条搜下去吧，稳T 我们发现这个状态可以记录一下（记忆化搜索），f[i]表示从i点找下去可以找到的终极消费者数目，状态转移很简单：
edge[i].to表示从i出发的边分别连向的点 终极消费者点的f=1 答案就是∑(f[生产者])
#include<bits/stdc++.h> using namespace std; bool flag=0,r[100001],c[100001]; int n,m,ans=0,f[100001]; int nedge=0,p[200001],nex[200001],head[200001]; inline void addedge(int a,int b){ p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge; } inline void dfs(int x){ if(f[x])return; int sum=0; for(int k=head[x];k;k=nex[k]){ flag=1;dfs(p[k]); sum+=f[p[k]]; } f[x]=sum; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y;scanf("%d%d",&x,&y); addedge(x,y);r[y]=1;c[x]=1; } for(int i=1;i<=n;i++)if(!c[i])f[i]=1; for(int i=1;i<=n;i++)if(!r[i]){ flag=0;dfs(i); if(flag)ans+=f[i]; } printf("%d",ans); return 0; }