Can someone please help tell me why I am getting WA for 131D - Метро or where my code goes wrong.
I get WA at test8 which is a very big test having 3000 nodes for which I am unable to debug.
Here's my submission. 11783845
My intended algorithm is as follows:
First find all the vertices in the ring(cycle) using
dfs().Then do DFS for each of the vertex in the ring to find the distance of each node from the ring. This is done by
dfs2()
This algorithm is the same as mentioned in the editorial
Seeking some help. Thank you. :)
Let me just tell you, How did i solve this problem.
Actually the main task is to find out the only back edge in the graph. Since the constraints are low i have found by removing each edge once. Although, we can do this task in linear time as well by maintained visiting time of each vertex.
Once you have found the back edge suppose (u,v) , remove that edge from the graph now realise that the graph is a tree which contains exactly one path from a node to every other node. find the path from u,v in this tree. Note that these are all those nodes which are going to be appeared in our one and only cycle. highlight these vertex with some random value ( i used 1 as this random value :P ). Now for all those vertices which are not highlighted do dis(x) = dis(parent) + 1 , subtract 1 from the final distances. I have coded this in the same way i described you can check my solution here.