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

Из оценки сложности, вроде, следует, что если у нас пара (u,v) входит в список запросов, то пара (v, u) тоже будет входить. Иначе не понятно откуда следует, что каждый запрос будет рассмотрен дважды. Если пары (u, v) нет, то данный псевдокод в вершине u запрос (v, u) никак не обработает. Ещё, в оригинальном псведокоде/статье, что я встречал, вершина помечается как посещённая/чёрная/т.п. уже после первого цикла с dfs (и перед просмотром запросов), а не до. Это вроде влияет на алгоритм, но насчёт конечного результата не уверен. --93.185.28.171 03:51, 31 октября 2016 (MSK)