Определите, является ли u предком v

Question

Вот проблема, и моя попытка решения.

Мое решение: 1. Запустить топологическую сортировку дерева, которая выполняется за линейное время BigTheta (E + V), где E - это число ребер, а V - количество вершин.Это помещает его в связанный список, который также занимает постоянное время.2. Вершина u будет предком, если у нее более высокое время окончания, чем у вершины v. 3. Посмотрите на 2 вершины в связанном списке и сравните их время окончания и верните true или false в зависимости от результата из шага 2.

Это звучит правильно или я что-то упустил?

Answer 1

Вот подход, который будет работать для любого дерева (не только двоичного).Шаг предварительной обработки - выполнить Euler Tour по дереву (это всего лишь обход DFS) и создать список из этого тура.Когда вы посещаете узел в первый раз, вы добавляете его в список, а когда вы посещаете его в последний раз, вы добавляете его в список.

Пример:

    x
   / \
  y   z

Список будетвыглядеть как: [b(x), b(y), e(y), b(z), e(z), e(x)].Здесь b(x) означает ввод x, а e(x) означает уход x.Теперь, когда у вас есть этот список, вы можете ответить на запрос is x an ancestor of y, выполнив тест b(x) is before b(y) and e(y) is before e(x) в списке.

Вопрос в том, как вы можете сделать это в постоянное время?

Для статических деревьев (что имеет место для вас), вы можете использовать таблицу поиска (он же массив) для хранения b/e, теперь проверка занимает постоянное время.Так что это решает вашу проблему.

Answer 2

Я не думаю, что вы понимаете, что означает «постоянное время», совершенно правильно.«... время BigTheta (E + V) где E - число ребер, а V - число вершин» равно линейное время, а не постоянное время.

Конечно, вам разрешено брать линейное время для предварительной обработки, так что это нормально, но как вы собираетесь выполнить свой шаг 3 («Посмотрите на 2 вершины в связанном списке») в постоянное время?