Hi, I'm just done like 40 submission of this problem (https://www.spoj.com/problems/GOODA/). I really stuck thinking why my solution get ac, pls help me. Give a directed graph, an array of value of each city, s — start city, e — end city and ask for choosing a path from s to e and the path have maximum value of city on the path. **Guarantee that e is reachable from s.**

I converting the directed graph to condensation graph (DAG) (by this technique https://cp-algorithms.com/graph/strongly-connected-components.html) and do dp. But i think in the first dfs(dfs1) I just need to dfs1 start from the s, in stead of staring from every node u that used[u] = false, bcuz e is reachable from s.

```
void dfs1(int u){
used[u] = true;
for(auto v : adj[u]){
if(!used[v]){
dfs1(v)
}
}
st.epb(u);
}
// the normal and get ac
for(int i = 1 ; i <= n ; i++){
if (!used[i]){
dfs1(i);
}
}
// ====
// i think problem just need to, but i get WA
dfs1(s);
// =====
```

Here is my code get ac, https://ideone.com/6KwRpb

Can u guys give me some test case that my think will wrong. Thanks for reading, sorry for my bad English :((

Auto comment: topic has been updated by txhai12 (previous revision, new revision, compare).ok b

You need to find strongly connected components and then condense the graph and then use dp on the condensed graph as per the topological ordering of the graph.

I believe this blog contains all the relevant details

Good luck :)

AC Code:

Spoilerhttps://pastebin.com/u2CcHmH4