拓扑排序例题 P4017 最大食物链计数-Toy模板网

这篇具有很好参考价值的文章主要介绍了拓扑排序例题 P4017 最大食物链计数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

拓扑排序例题 P4017 最大食物链计数

题目链接：P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

第一行，两个正整数 $n 、 m$ ，表示生物种类 $n$ 和吃与被吃的关系数 $m$ 。

接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

各测试点满足以下约定：

拓扑排序例题 P4017 最大食物链计数

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE ）文章来源地址https://www.toymoban.com/news/detail-424844.html

AC代码

#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(false); \
std::cin.tie(0);                             \
std::cout.tie(0)

#define all(v) v.begin(),v.end()

#define int long long
#define PII pair<ll,int>
#define ld long double
#define x first
#define y second
#define endl '\n'
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2e5+10;
int in[N],out[N];
int ans = 0;
queue<int> q;//拓扑排序队列
int num[N];//记录边长
vector<int> nei[N];//每个点分别邻接的点

//出度和入度
int n,m;
void solve()
{
    cin>>n>>m;
    //n个点，m条边
    for(int i = 1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        //x -> y
        ++in[y],++out[x];
        nei[x].push_back(y);
    }
    //入度为0的点
    for(int i = 1;i<=n;i++){
        if(in[i] == 0){
            num[i] = 1;//初始化
            q.push(i);
        }
    }
    while (!q.empty()){
        //当前点
        int top = q.front();
        q.pop();
        int len = nei[top].size();
        //遍历当前点的邻接点
        for(int i = 0 ; i < len ; i++){
            int next = nei[top][i];
            in[next]--;
            //删除当前结点，它的邻接点入度减一
            num[next] = (num[top] + num[next]) % 80112002;
            //更新邻接点的得到的边长

            if(in[next] == 0){
                q.push(nei[top][i]);
            }
            //如果邻接点入度为0，加入队列,作为一个单向图,最后一定会拓扑到终点
            //终点是出度为0的点
        }
    }
    for(int i = 1;i<=n;i++){
        if(out[i] == 0){
            ans = (ans + num[i]) % 80112002;
        }
        //如果是出度为0的点，说明是终点，加入答案
    }
    cout<<ans<<endl;
}
signed main(){

    solve();

}

到了这里，关于拓扑排序例题 P4017 最大食物链计数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！