PROBLEM LINK: CodeChef: Practical coding for everyone

I got the approach to solve the problem, even implemented it and got and AC too . but still I am not able to get that how are we ensuring that all the possible paths between any 2 nodes have been checked , I mean we are just performing a dfs and if we encounter a same vertex again then we compare it with the previous value distance value for it and return true or false accordingly. It would be great if somebody can please explain how are we ensuring its correctness?

COMMENTED CODE : CodeChef: Practical coding for everyone

Consider a large graph consisting of 1e5 nodes and edges.

Let’s call the source node x, and let’s say that there are two nodes y and z.

There are two paths from y to z, one with length ‘a’ and one with length ‘b’ where a≠b (so graph is not conservative)

Let’s say the length of path from x to y is c.

Then node z will be visited twice with distinct distances a+c and b+c. The function will return false.

If the function returns true then we can assume that there is no pair with different distance paths.

This will be true for any nodes x, y and z; therefore, the logic is valid.

1 Like

Thanks, a lot buddy

1 Like