| Submit | All submissions | Best solutions | Back to list |
PT07Z - Longest path in a tree |
You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.
Input
The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).
Output
Print the length of the longest path on one line.
Example
Input: 3 1 2 2 3 Output: 2
| Added by: | Thanh-Vy Hua |
| Date: | 2007-03-28 |
| Time limit: | 0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | Co-author Amber |
hide comments
|
||||||||||||||
|
2018-06-22 11:39:54
It just requires single dfs. Just add the longest and 2nd longest path from the source node. |
||||||||||||||
|
2018-06-19 18:31:02
Logic: Use two bfs. The first to find the farthest node from a particular node. That will be the leaf node. Again applying bfs on this will give you the maximum distance. |
||||||||||||||
|
2018-05-25 11:00:13
If your approach is correct you not need to worry about the root of the tree. Accepted in a Go! |
||||||||||||||
|
2018-04-10 04:45:17 yaswanth desu
If any one having doubt regarding the root means, consider the below example 3 1 2 2 3 Here 1 is the root. 4 1 2 2 3 4 1 Here 4 is the root. |
||||||||||||||
|
2018-04-09 20:48:03
What's the bfs+dp approach? |
||||||||||||||
|
2018-03-17 15:32:31
Why running two dfs solves the problem.I still do not get it. |
||||||||||||||
|
2018-03-14 03:02:36
Its a Tree diameter problem so you have 2 solutions to get AC with oneshot 1- using dfs little hard 2- using to bfs( First one to get the the furthest from any node then bfs with the the furthest you got ) |
||||||||||||||
|
2018-03-10 04:24:25
Yay AC in one go Python, using a single BFS + DP approach :D Fun problem! |
||||||||||||||
|
2018-02-02 14:22:24
the test cases of this question are weak..plz correct them.. 7 1 2 2 3 3 4 4 5 2 6 6 7 the correct output is 5 but my ACCEPTED code is giving 4....:P Last edit: 2018-02-02 14:24:05 |
||||||||||||||
|
2018-01-03 21:25:31
First did it in around september when I had no knowledge of DP, by using two BFS. Did it again with dp in January. Trust me, you'd love the DP idea. It's much more reliable than 2 BFSs. |
||||||||||||||
RSS