Vedkribhu's blog

Need Help TLE in only 1 subtask CSES Graph Problem. C++
By Vedkribhu, history, 4 years ago, In English

I was doing this graph problem from CSES link. I am getting TLE in only one sub task. I am new with c++, can you take a quick look, why it may fail for big sub task. Algorithm is just a simple BFS. My Code.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, since this question is about a DAG, you can first topological sort the graph and then do longest path dp.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, DP worked. But what do you mean by topologically sorting the graph, do we find the topological ordering (of vertices) and then do dfs according to that order? Here I don't see why require that as we have to go from Vertex-1 to vertex-n.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, topologically ordering the vertices.

      I think in general doing DP on DAG, the order from top sorting is the order you process the nodes in. Yes, 1 is start and n is end but you don’t know the order of the nodes in the middle and processing them in a wrong order should give you a wrong answer.

      For example if your graph is [{1, 3}, {3, 2}, {2, 4}] and you process the nodes in the order 1, 2, 3, 4 then you may get dp[1] = 0, dp[2]=inf, dp[3]=1, dp[4]=inf since when trying to fill in dp[2] we haven’t filled in dp[3] yet. Then when we try to fill in dp[4], we see that we have dp[2] incorrectly filled in with inf so we fill in dp[4] with inf+1

      → Reply