Problem
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.
Einschränkungen
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.
Beispiele
Eingabe:
edges = [
[1, 2],
[2, 3],
[3, 4],
[2, 5]
]
vertices = 5
Erwartete Ausgabe:
expected = 3Eingabe:
std::vector<std::vector<long long>> edges = {
{1, 2},
{2, 3},
{3, 4},
{2, 5}
};
long long vertices = 5;
Erwartete Ausgabe:
long long expected = 3;Eingabe:
long[][] edges = new long[][] {
new long[] {1, 2},
new long[] {2, 3},
new long[] {3, 4},
new long[] {2, 5}
};
long vertices = 5;
Erwartete Ausgabe:
long expected = 3;Erläuterung
The path 5–2–3–4 contains three edges. No path in this tree is longer.
Eingabe:
edges = []
vertices = 1
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<std::vector<long long>> edges = {};
long long vertices = 1;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long[][] edges = new long[][] {};
long vertices = 1;
Erwartete Ausgabe:
long expected = 0;Erläuterung
A single vertex has no edges, so the longest path length is 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
In einem Baum findest du den längsten Pfad mit zwei Graphdurchläufen statt, jedes Paar von Knoten zu prüfen.
Hinweis 2
Starte bei einem beliebigen Knoten, finde den am weitesten entfernten Knoten und suche dann von dort erneut, um die längste Distanz zu messen.
Hinweis 3
Zähle Kanten, nicht Knoten, und denk daran: Ein Baum mit nur einem Knoten hat den Durchmesser null.
Erwartete Komplexität
Zeit O(vertices), zusätzlicher Speicher O(vertices)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.