matavanga's blog

Graph problem (spoj) length of the longest path in a tree
By matavanga, 13 years ago, In English

i am trying to solve http://www.spoj.pl/problems/PT07Z/  problem.

i first got the most farthest point from root and then got the farthest point from that point
but i am getting TLE. can you please find the appropriate algorithm for this problem .
thanks




GOT AC!!! 
THANKS ALL.
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
If you want to stick to this approach, just replace Dijkstra with BFS.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    i tried but that also gives TLE .
    thanks

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Also I'd suggest that you replace "t=Integer.parseInt(lst[ind].get(i).toString());" with something more reasonable. It looks much like "if (booleanVar.toString().length()==4) {...}".
      → Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
plz use pastebin.com to post ur code
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
heights for the two largest in the tree, that is, the two leaves below you can find and the result is the sum of both heights
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Use just DP, using simple dfs you can calculate the two deepest nodes and returning the depths of his father, so that it can calculate where the maximum path length in one of its ends to the parent of the node.
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I also have a problem with this task. My code ( http://ideone.com/RhhwIC ) is getting WA, but I can't find a bad test case. I'm doing DFS to compute paths for all neighbours for all nodes (as a root) and for every node I join two biggest results.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have another inefficient approach for solving this problem. The approach would give TLE, but I want to confirm its validity. Please if you could confirm -

START -

1. Make a list of nodes of the Tree storing the "Degree" of each node along with the neighbors of the node. 

2.Initialize Length=0;

3. While there are nodes present in the tree, perform the following
   a. remove the nodes having degree 1. 

   b. if(number of nodes removed >2 ) length+=2 else length+=1

   c. update degree of node and its neighbors

return length

END.

So, here, what I am essentially doing is tapering down the longest path, starting from all the boundary(degree 1) nodes. Is the solution valid?

Thanks in advance !

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Your approach will yield a wrong answer on the following case:

    1---2---3---4

    In the first step you will remove 1 and 4 and update your length to 1. In the next step you will remove 2 and 3 and update length to 2. But as you can clearly see the longest path is from 1 to 4 of length 3.

    Changing your condition to (nodes removed>=2) will also yield a wrong answer in this case. But I think maybe changing your condition to (nodes removed >= 2) and also adding the case that:

    if(nodes left ==2) length++; return length;

    might give you the right answer. No guarantees on that though.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @Akul — Thanks for pointing out the bug. But, as you said, the Logic is yet to be verified.

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

how to find the longest path using dfs?

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

    Use two dfs . Firstly choose an arbitrary node a and find the farthest node b from a using dfs. Then find the farthest node c from b using dfs. The distance between b and c will the answer. Link for my code

    → Reply