Изменения

Перейти к: навигация, поиск

Алгоритм Тарьяна поиска LCA за О(1) в оффлайне

Нет изменений в размере, 01:51, 7 июня 2014
Нет описания правки
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предке.
Если он не минимальный, значит, есть на какой-то большей глубине, то есть такая вершина, которая была посещена раньше и для которой условия на <tex>u</tex> и <tex>v</tex< > выполнялись, значит, тогда должна была найтись эта вершина в качестве <tex>LCA</tex>.
[[file:mytree.png|500px|разные цвета {{---}} разные классы, а белые вершины ещё не просмотренные в dfs]]
Анонимный участник

Навигация