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
hide comments
|
hk_visact:
2017-08-23 13:02:50
AC in one go, applied 2 bfs, took a while to type the code in java though
|
|
vishesh197:
2017-08-19 17:19:19
use bfs then dfs (dynammic programming) |
|
sharma96:
2017-08-15 22:05:04
Can anyone please tell how to handle this test case:
|
|
Shantanu Banerjee:
2017-08-08 08:44:15
Simple Double DFS! |
|
sunidhi:
2017-08-04 06:17:12
@anuraag19 spoj won't allow us to see your solution.use some other platform to share your code.
|
|
anuraag19:
2017-08-02 18:51:15
does anybody know why i am getting runtime error?
|
|
karthik_vg:
2017-07-18 13:55:21
dfs + memorization ;) |
|
sagnik_66:
2017-07-05 10:48:57
Solved using single DFS, this helped : https://cptalks.quora.com/Diameter-of-a-Tree |
|
phben:
2017-07-04 03:24:22
@prashant2018 How to see the test cases? Aren't they hidden? |
|
ashwani0605:
2017-06-21 06:52:03
Some of the answer in SPOJ toolkit are wrong, so verify on your own |
| 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 |
RSS