In yesterday's Div2 E I was stuck at finding the shortest cycle. I was using dfs and each time a backedge (x,y) occurred I was keeping the minimum of level[x]-level[y]+1 only to realize it was wrong. The answer would depend on the order of dfs traversal. So I randomly shuffled adjacency lists few times and used dfs each time while keeping the minimum. I managed to pass all test cases. Is there any proof that the correct answer will be found with high probability with this approach or I just managed to be lucky?
I used the example I found yesterday here : https://stackoverflow.com/questions/20847463/finding-length-of-shortest-cycle-in-undirected-graph
Instead of one chain from A to C, I used 8 horizontal chains between B to D.
Gave 8 as the input to the following :
Yeah. So that was probably due to weak test cases. Thank you.