544. Farthest Two Towns
A mountain region has n towns numbered 0 to n - 1. The array edges lists the two-way roads, where edges[i] = [u, v] joins towns u and v. The roads connect all towns and contain no loops, so there is exactly one route between any two towns.
A courier company wants to know how far apart the two most distant towns are. Return the largest number of roads on the route between any pair of towns. If the region has a single town, the answer is 0.
Example 1
- Input:
- n = 7, edges = [[0,1],[1,2],[1,3],[3,4],[4,5],[4,6]]
- Output:
- 4
- Explanation:
The longest route is 2-1-3-4-5, which uses 4 roads.
Example 2
- Input:
- n = 5, edges = [[0,1],[0,2],[0,3],[0,4]]
- Output:
- 2
- Explanation:
Any two outer towns are joined through town 0, which takes 2 roads.
Example 3
- Input:
- n = 2, edges = [[1,0]]
- Output:
- 1
- Explanation:
The only two towns are directly connected by one road.
Constraints
1 ≤ n ≤ 105
edges.length == n - 1, 0 ≤ u, v < n
The edges form a tree: the graph is connected and acyclic.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)