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
bunnycoder:
2015-12-12 08:42:09
Be careful with the line one node to another costed me 1 WA simple dfs
|
|
Shantanu Banerjee:
2015-12-02 09:20:10
@Mohit Rathore The input will not be a forest.
|
|
Akshay Damle:
2015-10-27 23:14:53
AC in 1 go :) This Quora answer was helpful: https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work |
|
satish9040:
2015-10-27 15:06:14
http://apps.topcoder.com/forums/?module=Thread&threadID=794604&start=0&mc=3#1758019 |
|
snehil10111995:
2015-10-17 13:41:56
@Mohit, your given graph is not a connected tree. Rather it is a forest with two trees. |
|
Mohit Rathore:
2015-10-17 07:13:43
Am I misunderstanding the question? For this test case answer should be 3 (4->5->6->7)
|
|
kejriwal:
2015-10-12 10:16:36
nice one ! |
|
[Mayank Pratap]:
2015-10-10 17:03:08
this time using DFS :) |
|
f3l1pe:
2015-10-05 02:58:52
Si hay alguno de la UTN lo puede resolver, que me mande un mail a lopezfelipeutn@gmail.com con su código; Estoy buscando miembros para competir |
|
sneh sajal:
2015-09-21 15:13:16
normal recurrsion to get max level!! or you can say bfs or dfs :)
|
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 |