Removing each edge and doing bfs is too costly. In stead, we remove each vertex and do BFS finding shortest and second shortest path to each node via a different children from root. Here's my code : http://ideone.com/sCOHAQ