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
|
newbie:
2016-01-30 14:18:18
answer is 5 |
|
|
newbie:
2016-01-30 14:17:44
simple dfs accepted in 0.00 s
|
|
dwij28:
2016-01-15 06:29:00
Did it by using bfs twice, what is the dfs way of doing it ? If anyone could please provide some helpful link for solving it with dfs.. |
|
dark_lord1:
2015-12-26 00:12:43
Using a 2D matrix of type char to store edge information gives runtime error..But using adjacency list to store graph give AC....How can the 2D matrix possibly exceed memory available?? Costed me 2 RE. :( |
|
vedang:
2015-12-25 18:23:38
Don't know why but when I changed memset to fill_n in my C++ code, WA turned into AC! |
|
the_sage:
2015-12-18 11:30:44
the tree should not have a cycle but the test cases have a cycle in them for example
|
|
|
the_sage:
2015-12-18 11:18:19
for the test case
|
|
codelover25:
2015-12-17 16:36:48
AC in 1 go :) Just be careful with ordering of tree. |
|
piyush9620:
2015-12-15 11:20:08
http://www.spoj.com/users/markroxor
|
|
maverick_10:
2015-12-13 11:59:00
Ooh, finally I am learnig graphs!!!
|
| 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