Блог пользователя Vedkribhu

Need Help TLE in only 1 subtask CSES Graph Problem. C++
Автор Vedkribhu, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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

      → Ответить