Ближайший общий предок

Дано корневое дерево
Необходимо найти самого низкого общего предка для двух вершин

Пусть дерево задано массивом, где p_i - предок вершины i и H - максимальная высота дерева. Тогда задача решается за O(H) двумя циклами от вершины к корню.

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

Листинг C++

// lowest common ancestor
int lca (vector < int > &prev, int &a, int &b)
{
    vector < int > is (prev.size (), 0);

    for (int i = a; i >= 0; i = prev[i])
        is[i] = 1;
    for (int i = b; i >= 0; i = prev[i])
        if (is[i])
            return i;

    return - 1;
}

07.09.2008, 13:56

По всем вопросам обращаться: rumterg@gmail.com