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
arpitscoding:
2016-09-26 17:14:54
f you! 5th test case. |
|
rkasat:
2016-09-26 00:06:57
one bfs to find the farthest node. second bfs to find the longest path. AC in one go! |
|
Kuldeep Fouzdar:
2016-09-25 19:02:27
CLRS(3rd edition) #22.2-8 |
|
vishalsingh:
2016-08-20 17:02:42
how one knows which test case my solution fails
|
|
Himanshu Sharma:
2016-08-14 03:12:59
single dfs, my 50th ;-[] |
|
Surbhi:
2016-08-07 17:31:32
Why is adjacency matrix not working? |
|
saurabh789:
2016-07-11 13:10:07
use dfs two times first time to find a node "s" which is at max distance from any child node, next time use "s" as starting node and find length of longest path |
|
sumit suthar:
2016-07-07 14:51:28
double dfs easy one.. |
|
Suryansh Agnihotri:
2016-07-01 12:28:32
It is having weak test cases , one of my wrong solution got accepted. |
|
ajay_raj:
2016-06-29 19:44:23
Last edit: 2016-07-01 03:48:57 |
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 |