Virtual_Contestant's blog

E-Olymp BFS problem
By Virtual_Contestant, history, 6 years ago, In English

Can anyone please explain me the problem? i have been trying hard to understand this. https://www.e-olymp.com/en/contests/16462/problems/170299 the asked for maximum distance so in their second testcase isn't from 4 to 5 the distance is minimum?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Given a directed graph with n vertices and m edges. Find the maximum shortest distance from some vertex to the given vertex s.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It asks for the distance, not the node. 4 is the distance from the farthest node to S.

Just build the inverted graph and do one single BFS from S. The maximum depth of the BFS is the answer.

→ Reply