Problem: Link I was using Bellman Ford to solve this. To detect a cycle in bellman ford we usually do one more pass on the edges (after n-1) passes and see if anything updated, if yes there is a cycle. But in this problem even if there is a cycle in graph but not a part of path between vertex 1 and n is tolerable. How to detect when to print -1?
Run the Bellman-Ford Algorithm for the nth iteration and mark the nodes whose distance is changed. Now reverse the adjacency list and run a DFS from node 'n'. If at least one of the nodes marked is visible from n, then the answer is -1, else the answer is the maximum distance from 1 to n.
Can you please explain the intuition behind doing this?
Only to check that, does a positive cycle in the graph affects the 'nth' node, if it does, then it is sure that answer is -1, else answer is the max distance.
Ex:
7 7
1 2 1
2 7 1
1 6 -1
6 5 -1
5 4 -1
4 3 -1
3 1 5
here, the +ve cycle affects the 'nth' node.
But here,
8 9
1 2 1
2 3 1
3 4 1
4 2 1
1 8 1
5 8 1
5 6 1
6 7 1
7 5 1
it doesn't affect the nth node.
Reason behind marking nodes whose distances are changed in the nth iteration — node which is marked is involved in the cycle. We will print -1 only when it is possible to reach to last node from the cycle. To check whether it is possible to reach to last node from the cycle, there are two ways 1) run dfs from every node which is marked (involved in cycle) and check whether is it possible to reach to nth node, if yes print — 1. 2)reverse the graph and check whether it is possible to reach to atleast one node which is marked from the last node, if yes print -1. Both ways give the same result but the 2nd method is fast. Please ask if you have any doubt(this is my first explanation, I apologize if my explanation is not clear).
what if the node (in the cycle and connected to n) is not connected to 1?
1 4 1
2 4 1
2 3 1
3 2 1
there's a cycle 2 — 3 — 2 and 2 is connected to 4 but even then, answer is still 1 (and not -1) because we can't go to that cycle
what I did was see everyone that could be in a path from 1 to n, if one of those nodes are in a cycle, answer is -1:
run dfs from 1 in original graph, mark everyone connected
run dfs from n in reversed graph, mark everyone connected
intersection is the vertices that we can use in our path, and if any vertex here is in a cycle, ans is -1
Nodes that are not reachable from node 1 will always remain unchanged i.e INFINITY in the distance array. so only dfs from n'th node in reverse adj list is fine .
It's a super confusing question as expected from cses: example 1:
WHY?????????
it's a simple bellman-ford algorithm
will not work for
4 4 1 4 1 2 4 1 2 3 1 3 2 1
Answer is -1, but it isn't infinity score.
?
xd