Can anyone tell me what I am missing in this solution for SPOJ-KFSTB problem.

Revision en2, by kritak, 2021-05-18 21:04:00

SPOJ-KFSTB

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();
}

}

Tags #dfs, # dp, #spoj

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English kritak 2021-05-18 21:05:25 0 (published)
en3 English kritak 2021-05-18 21:04:40 4
en2 English kritak 2021-05-18 21:04:00 72 (saved to drafts)
en1 English kritak 2021-05-18 19:19:53 1115 Initial revision (published)