Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Кратчайшее расстояние в дереве

Дано корневое дерево
Необходимо найти кратчайшее расстояние между парой вершин

Решением является сумма расстояний от этих вершин до их LCA.

Асимптотика: O(H).


Листинг C++

// least distance in a tree
int ldt (vector < int > &prev, int &a, int &b)
{
    int d1 = 0;
    int d2 = 0;
    vector < int > is (prev.size (), 0);

    for (int i = a; i >= 0; i = prev[i])
        is[i] = ++ d1;
    for (int i = b; i >= 0; i = prev[i], ++ d2)
        if (is[i])
            return is[i] + d2 - 1;

    return - 1;
}

07.09.2008, 14:00