Question about SCCs in specific problem !

Revision en1, by txhai12, 2021-11-29 12:48:46

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 :((

Tags graphs, sccs, question

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English txhai12 2021-11-29 12:49:25 16
en1 English txhai12 2021-11-29 12:48:46 1261 Initial revision (published)