11428. Диаметр дерева

Дано дерево, состоящее из n вершин.

Диаметр дерева – это максимальное расстояние между двумя вершинами. Найдите диаметр заданного дерева.

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 2 * 10⁵) – количество вершин в дереве. Вершины пронумерованы числами от 1 до n.

Каждая из следующих n – 1 строк описывает ребро и содержит два целых числа a и b (1 ≤ a, b ≤ n), обозначающих, что вершины a и b соединены ребром.

Выход. Выведите одно целое число – диаметр дерева.

Пример входа	Пример выхода
5 1 2 1 3 3 4 3 5	3

РЕШЕНИЕ

графы – поиск в глубину

Анализ алгоритма

Выполним поиск в глубину, начиная с любой вершины, например, с вершины 1. Найдём вершину, наиболее удалённую от 1, и обозначим её как вершину a. Затем запустим поиск в глубину из вершины a и найдём вершину, которая будет наиболее удалённой от a. Обозначим её как вершину b. Тогда расстояние между вершинами a и b будет максимальным и равно диаметру дерева.

Пример

Рассмотрим дерево из примера.

Диаметр дерева равен 3. Наибольшее расстояние достигается, например, для вершин 2 и 5.

Упражнение

Найдите диаметр дерева.

Реализация алгоритма

Входное дерево храним в списке смежности g. Кратчайшие расстояния от источника до вершин сохраняем в массиве dist.

vector<vector<int>> g;

vector<int> dist;

Функция dfs выполняет поиск в глубину из вершины v. Кратчайшее расстояние от источника до вершины v равно d. Предком вершины v при поиске в глубину является p.

void dfs(int v, int d, int p = -1)

{

Сохраняем в dist[v] кратчайшее расстояние от источника до вершины v.

dist[v] = d;

Перебираем все ребра (v, to). Для каждого сына to вершины v (где to не является предком v) запускаем поиск в глубину. Расстояние от источника до вершины to будет равно d + 1.

for (int to : g[v])

if (to != p) dfs(to, d + 1, v);

}

Основная часть программы. Читаем входные данные.

scanf("%d", &n);

g.resize(n + 1);

dist.resize(n + 1);

Строим неориентированное дерево.

for (i = 1; i < n; i++)

{

scanf("%d %d", &u, &v);

g[u].push_back(v);

g[v].push_back(u);

}

Ищем кратчайшие расстояния от вершины 1 до всех остальных вершин. Самой удаленной от нее вершиной является a.

dfs(1, 0, -1);

a = max_element(dist.begin(), dist.begin() + n + 1) –

dist.begin();

Ищем кратчайшие расстояния от вершины a до всех остальных вершин. Самой удаленной от нее вершиной является b.

dfs(a, 0, -1);

b = max_element(dist.begin(), dist.begin() + n + 1) –

dist.begin();

Выводим диаметр дерева – кратчайшее расстояние от a до b.

printf("%d\n", dist[b]);