最开始看见这道题目的时候，首先想到的是用DFS或BFS试一试，如果用DFS，显然超时妥妥的，BFS的话，由层层递推的关系我们可知，若以某个结点为重点，则最终到该点的食物链总条数num为其所有前驱结点总条数num之和，
然而，BFS显然不行，因为对于某个结点来说，其在食物链中可能占有多个不同级数，只有当这些不同在不同级数上求得的num结果全部得到后，才能将最终结果纳入其后驱结点的num中，这个思路已经很明确了，拓扑排序！
给你一个食物网，你要求出这个食物网中最大食物链的数量。（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）Delia 非常急，所以你只有 1 秒的时间。由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。
#include<iostream> #include<queue> #include<vector> using namespace std; int main(){ int n,m; //n种动物，m条边 cin >> n >> m; vector<int> a[n+1]; int book[n+1] = {0}; //记录入度 int num[n+1] = {0}; queue<int>q; for(int i = 0;i < m;i++){ int x,y; cin >> x >> y; a[x].push_back(y); book[y]++; } for(int i = 1;i <= n;i++){ if(book[i] == 0){ q.push(i); num[i] = 1; // 每个生产者代表一条新路径开始 } } int aim = 0;//记录最终结果 while(!q.empty()){ int x = q.front() ; q.pop() ; if(a[x].size() == 0){ aim += num[x]; if(aim >= 80112002) aim %= 80112002; } else for(int i = 0;i < a[x].size() ;i++){ num[a[x][i]] += num[x]; if( num[a[x][i]] >= 80112002) num[a[x][i]] %= 80112002; //注意num的结果可能会超限制int的限制！ book[a[x][i]]--; if(book[a[x][i]] == 0) q.push(a[x][i]); } } cout << aim; return 0; }
原文：https://www.cnblogs.com/LISIYUWANG/p/13334948.html