I solved this problem: http://www.spoj.com/problems/PT07Z/
Basically, we have to find the length of longest path in a tree. I solved this problem by applying BFS two times. First to find the farthest node from ‘1’ and then started a BFS from that node. When I searched on the internet, many people had used the same method. But some people had used single DFS too. I still don’t get it. Can anyone explain me how we can solve this problem using DFS?
This should be a good read for your question :-
Double DFS
(Read the answer by Raziman).
Edit 1: My bad - didn’t read that you wanted “SINGLE” dfs approach. Will update soon(if unanswered).
Edit 2: Here is the single DFS thread on CSE - Single DFS
Although this has nothing to be linked with your answer above and even I solved the question above way mentioned, but can’t it be done by negating all the edges and then finding the shortest path? Will not that give me the length of longest path? I just want to check whether the approach is correct or not…
I dont get what you mean by “NEGATING all edges”. It is an un-directed and un-weighted graph. What does negating mean in this scenario ?
Oh,I misread the question as weighted I suppose, then negating means if the edge from any vertex u to v is x, then make it as -x.
Yes, afaik, you can treat a longest path problem in a weighted graph to be a shortest path problem in the same graph after negating edge weights but you will have to use algorithms that can handle negative edge weights.
Hey, thanks 