题目

现有n扇门，门之间有m种关系，门与门之间可以互相传送。将所有不能被传送到的门视为起点，将不能传送到其他门的门视为终点，利用这些传送关系，求出有多少种路线。
结果可能很大，请对998244353取模。
https://ac.nowcoder.com/acm/contest/82881/B

Input

5 7
2 3
1 2
4 5
1 3
2 5
3 4
3 5

Output

5

说明

共有
5 -> 4 -> 3 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 3 -> 1
5 -> 3 -> 2 -> 1
5 -> 2 -> 1
五条路线

题解

思路分析

STD

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N=5e3+5;
constexpr LL Mod=998244353;
int n,m,in[N],out[N],d[N];
vector<int> e[N];

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        in[x]++;
        e[y].push_back(x);
        out[y]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!in[i]){
            d[i]=1;q.push(i);
        }
    }
    
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto it:e[t]){
            d[it]+=d[t];
            d[it]%=Mod;
            if(!--in[it]) q.push(it);
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        if(!out[i]){
            ans+=d[i];
            ans%=Mod;
        }    
    }
    
    cout<<ans<<endl;
    return 0;
}