题意:有\(n\)个点,连\(m\)条边,求最多有多少条食物链(从头走到为有多少条路径).

题解:之前抽了点时间把拓扑排序补完了,这题其实就是一道拓扑排序的裸题.关于拓扑排序:

​ 1.首先,我们用\(in\)记录某个点的入度,\(out\)表示这个点向外所连的点.

​ 2.遍历所有点,找到入度为\(0\)的点,将其入队.

​ 3.遍历队列(将队头元素记录并存入答案后弹出),将入度为\(0\)的点所连边一条一条的消去,即所有的\(out[x]=-1\),且该点所连的点的入度都需要\(-1\),如果某点的入度为\(0\),将其入队.

​ 4.最后我们所得到的一定是某一种情况的拓扑序列.

那么对于该题,我们在求拓扑序列的同时,还要记录一下路径数,我们先使所有入度为\(0\)的点的路径数为\(1\),然后每次向外求拓扑序列时,对所有出边的点记录一个前缀和,最后累加一下出度为\(0\)的点的前缀和即可.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 80112002 ;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

int n,m;
int u,v;
int num[N];
vector<int> out[N];
vector<int> in(N,0);
vector<int> res;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>u>>v;
        in[v]++;
        out[u].pb(v);
    }
    queue<int> q;
    for(int i=1;i<=n;++i){
        if(in[i]==0){
            num[i]=1;
            q.push(i);
        }
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();

        res.pb(now);
        for(auto w:out[now]){
            if(w!=-1){   //如果这条边存在
                in[w]--;
                num[w]=(num[w]+num[now])%mod;
                if(in[w]==0){
                    q.push(w);
                }
                w=-1;   //删去这条边,但好像没什么用?
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        if(out[i].empty()){
            ans=(ans+num[i])%mod;
        }
    }
    printf("%d\n",ans);

    return 0;
}