Đề bài
A tree is a connected undirected graph with no cycles. Its diameter is the largest number of edges on a path between any two vertices. Return that length; you do not need to return the path. No root is specified.
Implement tree_diameter(vertices, edges).
Input
vertices: The number of vertices.
edges: Undirected connections [u, v].
Output
Return the diameter measured in edges, not vertices.
Ràng buộc
1 ≤ vertices ≤ 200,000. Exactly vertices − 1 edges, with distinct endpoints in 1…vertices. Inputs always form a tree. A one-vertex tree has diameter 0.
Ví dụ
Đầu vào:
edges = [
[1, 2],
[2, 3],
[3, 4],
[2, 5]
]
vertices = 5
Kết quả mong đợi:
expected = 3Đầu vào:
std::vector<std::vector<long long>> edges = {
{1, 2},
{2, 3},
{3, 4},
{2, 5}
};
long long vertices = 5;
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long[][] edges = new long[][] {
new long[] {1, 2},
new long[] {2, 3},
new long[] {3, 4},
new long[] {2, 5}
};
long vertices = 5;
Kết quả mong đợi:
long expected = 3;Giải thích
The path 5–2–3–4 contains three edges. No path in this tree is longer.
Đầu vào:
edges = []
vertices = 1
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<std::vector<long long>> edges = {};
long long vertices = 1;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[][] edges = new long[][] {};
long vertices = 1;
Kết quả mong đợi:
long expected = 0;Giải thích
A single vertex has no edges, so the longest path length is 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
In a tree, the longest path can be found by two graph searches instead of checking every pair of vertices.
Gợi ý 2
Start from any vertex, find the farthest vertex, then search again from there to measure the longest distance.
Gợi ý 3
Count edges, not vertices, and remember a single-vertex tree has diameter zero.
Độ phức tạp mong đợi
O(vertices) time, O(vertices) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.