Тема: lca методом двоичного подъёма
В dfs'е мы запоминаем вершины, которые уже посетили, но ведь у нас граф - это заведомо дерево, и такое запоминание лишнее. Или я что-то упустил из виду?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Feedback » lca методом двоичного подъёма
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
В dfs'е мы запоминаем вершины, которые уже посетили, но ведь у нас граф - это заведомо дерево, и такое запоминание лишнее. Или я что-то упустил из виду?
Да, вы правы, массив used совсем не обязателен, достаточно лишь сравнения с текущим предком - p.
Исправил код.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Feedback » lca методом двоичного подъёма