1 Тема от DimaV

  • DimaV
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-02-28
  • Сообщений: 1

Тема: Поиск LCA. Алгоритм Тарьяна на DSU.

Возникла проблема с пониманием алгоритма, который описан здесь - http://e-maxx.ru/algo/lca_linear_offline sad

Не понятно по какому принципу мы объединяем вершины в классы, и как потом выделяем представителя класса, который, как я понял, и является наименьшим общим предком.

Те, кто сталкивался с данным алгоритмом, разъясните, пожалуйста.... hmm

2 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: Поиск LCA. Алгоритм Тарьяна на DSU.

Мы запускаем обычную рекурсию, когда возвращаемся по ребру U -> V, обьеденяем два множества этих, при этом предком множества где лежит V (SET_ID(V)) ставим множество где лежит U (SET_ID(U)) -> P[SET_ID(V)] = SET_ID(U).

Теперь когда всё поддерево даннйо вершины U рассмотрено, мы просто начинаем бежать по запросам, которые связаны с U, Допустим это запрос U -> V, при
том мы смотрим что вершину V лежит в поддереве U,теперь что бы узнать их LCA,мы просто смотрим P[SET_ID(V)],что означает что мы смотрим предка который будем LCA для всего множества SET_ID(V).

Лучше всего написать и тщательно отладить или на листочке нарисовать и проделать ручной проход, тогда всё станет ясным.