Miku

很水的拓扑排序+dp

看错题除外。

这道题是要求有多少条食物链满足

左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费

不是求最长的多长或者有几条最长！！

(把一些无关紧要的变量起一些人名真有意思)

#include<iostream>
#include<queue>

using namespace std;
queue<int> q;

struct lian{
    int to;
    int next;
}lb[5000010];
int le[201000];
int head[200100];
int t=0;
int dp[2000010];
int n,m,ans;
int ind[500001];
void add(int from,int to){
    lb[++t].next=head[from];
    lb[t].to=to;
    head[from]=t;
}
int AA;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int k,j;
        cin>>k>>j;
        add(j,k);
        ind[k]++;
    }
    for(int i=1;i<=n;++i){
        if(!ind[i]){
        q.push(i);
        le[i]=1;
        dp[i]=1;
        }

    }
    while(!q.empty()){
        int u;
        u=q.front();q.pop();
        if(head[u])
        for(int i=head[u];i;i=lb[i].next)
        {
            int v=lb[i].to;
            le[v]=max(le[v],le[u]+1);
            dp[v]+=dp[u];
            dp[v]%=80112002;
            if(!--ind[v]) q.push(v);
        }else{
            AA+=dp[u];
            AA%=80112002;
        }
    }
    cout<<AA;
    return 0;
}