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

Need help in solving cses graph problem.
Автор Danish_amin_01, история, 4 года назад, По-английски

Below is the question link. https://cses.fi/problemset/task/1197 In this question I was thinking to get all cyclic paths and then go through all of them to get if any path has a negative value, if there is such a value then just print it and break the loop there itself. But I am having problem in printing all cyclic paths. :(

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

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

Use Bellman-Ford

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

    My first thought was Bellman-Ford but how do you print a negative cyclic path using Bellman-Ford and other issue was it has a huge time complexity. Do you have some other ideas?

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

      The code in the link above prints the path, and the complexity is $$$O(N*M)$$$ where N is number of vertex and M number of edges. This will work for the given constraints.

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

    i can't wrap my head around the parents, can you help me understand why parents will always lead to the right path?

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

      We basically to a DFS in the graph, so each vertex has some parent, which is the vertex visited just before the current one.

      In the implementation x is the vertex visited in nth loop. Since the longest possible cycle includes only n vertex, a vertex that changes in the nth loop is allways one on a negative cycle. Since in the DFS we had allways set p[v]="parent of v", p[i]->i is exactly such cycle.

      Note that there is not "the right path", since there could be more than one such cycle in the graph, we just have to find any one.

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

        I still don't understand, how are you referring it similar to a DFS? if i am not wrong, in bellman Form, we really don't follow edges in any order right? it might be possible that we are taking some other path's to edge to point to one of node in our actual path ( i know there can be multiple ), and it could mess up all the negative cycle. why is this not happing in the above mentioned solution? is there any more indepth reference for this ? i am having hard time grasping it :(.

        → Ответить