原题链接 https://www.luogu.org/problem/P3183
一道经典的拓扑排序的题目~
直接说思路吧：
1. 在输入的过程中，我们要统计每个点的出度和入度；
2. 进行一遍拓扑排序，同时给每个点维护一个 sum 值，表示从起点（入度为0的点）走到这个点有多少种方案，对于每条边的终点，它的 sum 值都要加上这条边起点的 sum 值；
3. 如果有一个点的出度为 0，那么就说明这条食物链已经走到了最高级消费者，我们将答案加上这个点的 sum；
4. 最后输出答案就好了；
说的有点快？来个样例解释一下下：
我们先找到入度为 0 的点：
进行拓扑排序：
挺详细了吧（逃~
下面上AC代码喽：
#include<iostream> #include<cstdio> #include<queue> using namespace std; int read() { char ch=getchar(); int a=0,x=1; while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) x=-x; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { a=(a<<1)+(a<<3)+(ch-‘0‘); ch=getchar(); } return a*x; } const int mod=80112002; int n,m,u,v,ans,edge_sum; int in[200001],out[200001],head[400001],sum[200001]; struct node { int id,len,to,next; }a[500001]; void add(int from,int to) { edge_sum++; a[edge_sum].next=head[from]; a[edge_sum].to=to; head[from]=edge_sum; } void topo() { queue<int> q; for(int i=1;i<=n;i++) { if(!in[i]&&out[i]) //题目中说一个孤立的生物不能算一条食物链,也就是说起点还要有出度 { q.push(i); sum[i]=1; //起点的方案数只能是1 } } int f; while(!q.empty()) { f=q.front(); q.pop(); if(!out[f]) //如果发现这个点出度是0,统计到答案里 { ans+=sum[f]; continue; } for(int i=head[f];i;i=a[i].next) { int zd=a[i].to; sum[zd]+=sum[f]; //终点的sum+=起点的sum in[zd]--; if(!in[zd]) q.push(zd); } } printf("%d\n",ans); //最后答案 } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { u=read(); v=read(); add(u,v); in[v]++; //统计入度 out[u]++; //统计出度 } topo(); //拓扑排序 return 0; }
原文：https://www.cnblogs.com/xcg123/p/11295782.html