http://www.spoj.com/problems/PT07Z/
This task is solved with 2 BFSs. (If you need more info about BFS go here). Here is how its done. First of all we need to start a BFS from any node we want and find the furthest node from the starting node. But wait, the path we just found isn't the longest, the node we just found is the starting point for our real longest path. Now we need to find the furthest node from the node we just found, that will be our answer.
So , for summarizing, we need 2 BFS, the first one starts with any node and ends on some node X.Xis the furthest form the starting node. Then the second BFS finds the furthest node from X. and the path is the path between those 2 nodes. Check my source code for a better understanding..
This task is solved with 2 BFSs. (If you need more info about BFS go here). Here is how its done. First of all we need to start a BFS from any node we want and find the furthest node from the starting node. But wait, the path we just found isn't the longest, the node we just found is the starting point for our real longest path. Now we need to find the furthest node from the node we just found, that will be our answer.
So , for summarizing, we need 2 BFS, the first one starts with any node and ends on some node X.Xis the furthest form the starting node. Then the second BFS finds the furthest node from X. and the path is the path between those 2 nodes. Check my source code for a better understanding..
Source code link not opening
ReplyDelete