Danish_amin_01's blog

Need help in solving cses graph problem.
By Danish_amin_01, history, 4 years ago, In English

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

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

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

Use Bellman-Ford

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

    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?

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

      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.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

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

      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.

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

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

        → Reply