Magikarp's blog

TLE in graph problem (spoj PT07Z) using java. Longest path in a tree.
By Magikarp, 12 years ago, In English

Hi!

I am trying to solve this problem: http://www.spoj.com/problems/PT07Z/ . I am trying to find the diameter of the tree by using double BFS but I am getting TLE. Here is my code:

http://ideone.com/vC9vsd

Thank you.

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

»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You don't need to use a map neither a BitSet, that could be taking a lot of time, instead make a simple array for represent the tree and a boolean array to mark visited nodes.

I think a DFS would be a better approach.

→ Reply