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
|
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.
|
|
bohot_hard_123:
2019-12-23 03:31:46
also many many thanks to @ jame_boy to sharing further in comment box
|
|
emtiaz_001:
2019-12-20 16:17:36
the moral of the story is to find the root correctly and calculate the distance from the rooooooooottttttttttt........ |
|
rmcr714:
2019-11-26 15:30:20
is it a tree problem because there is cycle present like 1 2 2 3, or do i need to learn graph for this |
|
hetp111:
2019-11-12 09:40:11
easier then it looks... calc height of each node. then for every node find 2 child with largest height. |
|
ishancosmos25:
2019-10-13 02:08:53
https://discuss.codechef.com/t/longest-path-in-a-tree-using-dfs-and-double-bfs/8893 for reference..
|
|
scolar_fuad:
2019-09-04 06:04:59
Simple dfs problem ...
|
|
jame___boy:
2019-08-30 00:30:33
many many thanx @anand_undavia for sharing the link.......
|
| 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