I am using dp with dfs to calculate the number of paths to each point. Can somebody tell me what am I missing?

const int mod = 1e9 + 7;

void solve () {

int C, B, S, T; cin >> C >> B >> S >> T; vector<ll> graph[C + 1]; vector<bool> vis(C + 1); for (int i = 0; i < B; i++) { ll x, y; cin >> x >> y; graph[x].push_back(y); } vector<ll> dp(C + 1); dp[S] = 1LL; stack<ll> st; st.push(S); while (!st.empty()) { ll v = st.top(); st.pop(); vis[v] = true; for (ll u: graph[v]) { dp[u] = (dp[u] + dp[v]) % mod; if (!vis[u]) st.push(u); } } cout << dp[T] % mod << "\n";

}

int main() {

ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { solve(); }

}

"Have you tried the following:

98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms."

The idea of using DFS is wrong. Let say there is path from 'A' to 'B' and your dfs chooses this path, now the possibility is that there can be other paths merging in this path, but since you already visited the previous path you will not update the result. Use topological sort instead.

Consider these edges exist in input

so you will push x and a in queue and value of dp[x] will be 1 when you wil pop it out. Now you will add dp[x] to dp[t]. But you must have noticed that there are 2 ways of reaching x

So you should have added 2 in dp[t].

If you want to use bfs you have to do it topologically i.e. only push x in queue when all of its parents have been pushed in and popped out of queue.