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
saurabhshadow:
2020-05-29 20:42:24
If you still stuck at this:
|
|
nature95:
2020-05-14 13:03:23
Used bfs two times.
|
|
offamitkumar:
2020-05-04 19:33:55
AC in single graph traversal . Just keep track of 3 things :
|
|
gnuzinhoo:
2020-05-02 16:05:00
I solved it using two bfs |
|
yourmom__:
2020-04-23 08:18:56
Java people, Scanner wont cause TLE in this question. I used scanner and got AC. |
|
zoso_floyd:
2020-04-15 14:42:57
Apply bfs two times. https://www.geeksforgeeks.org/longest-path-undirected-tree/ should help. |
|
aditya_shukla:
2020-03-30 14:26:15
Avoid using Scanner class in Java for taking input. |
|
blackhat_130:
2020-03-26 00:09:01
Beginner level problem for those who want to learn dfs.
|
|
unafraidofdog:
2020-02-10 05:25:13
Last edit: 2020-02-10 07:06:16 |
|
bohot_hard_123:
2019-12-23 03:31:46
also many many thanks to @ jame_boy to sharing further in comment box
|
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 |