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

#include<iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int N=2e5+100;
const int mod=80112002;
int n,m;
vector<int>g[N];
int din[N],dout[N];
queue<int>q;
int res[N],ans=0;
void toposort()
{
    for(int i=1;i<=n;i++)
    {
        if(din[i]==0)
        {
            q.push(i);
            res[i]=1;//记录到该点的食物链的条数，因为入度为0，所以为食物链起始点，计为1
        }
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(auto i:g[t])
        {
            res[i]+=res[t];//到该点的食物链条数为 他与他的前一节点的食物链条数相加
            res[i]%=mod;
            din[i]--;
            if(din[i]==0)
            {
                if(dout[i]==0)//出度为0的生物节点已经是该条食物链的顶点
                {
                    ans+=res[i];
                    ans%=mod;
                }
                q.push(i);
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        dout[x]++;//该生物的出度
        din[y]++;//该生物的入度
    }
    toposort();
    cout<<ans;
    return 0;
}