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
|
prasoonbatham:
2017-03-05 19:41:38
Easy two DFS :) |
|
kingp:
2017-03-03 09:43:30
is there any need for bfs in a tree there is only one path between any two vertices so dfs is enough. |
|
da_201501181:
2017-03-02 21:45:52
AC in one Go! Simple double dfs |
|
gboduljak:
2017-02-15 22:24:33
should be moved to tutorial |
|
scorpion_ajay:
2017-01-31 12:58:14
did it with both bfs and dfs, try both :) |
|
Chisty:
2017-01-02 19:56:23
I got accepted with Adjacency Matrix in C++. bool graph[10001][10001] is okay as global variable. |
|
hasan356:
2016-12-29 08:15:30
learned bfs!!
|
|
rez_wan_28:
2016-12-18 10:44:44
simple bfs..
|
|
cjycjy:
2016-11-10 04:49:01
Longest path dosen't stand for the deepth of the tree. So naive was I :( |
|
jawad_cs:
2016-11-06 08:45:58
Do not use Adjacency Matrix ull get a tle, use Adjacency List. |
| 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