Submission #75559061

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int mod = 998244353;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        vector<int>dp(n+1);
        dp[1] = 1;
        vector<vi>adj(n+1);
        vector<int>deg(n+1);
        for(int i = 1; i<=m; i++){
            int x,y;
            cin >> x >> y;
            adj[x].push_back(y);
            deg[y]++;
        }
        queue<int>q;
        for(int i = 1; i<=n; i++){
            if(!deg[i])q.push(i);
        }
        while(sz(q)){
            int cur = q.front(); q.pop();
            for(int nxt: adj[cur]){
                deg[nxt]--;
                dp[nxt] += dp[cur]; dp[nxt] %= mod;
                if(deg[nxt] == 0)
                    q.push(nxt);
            }
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

Submission Info

Judge Result