24
правки
Изменения
м
Исправлена описка
Покажем, что найдём наименьшего предка. Пусть это не так. Тогда существует какая-то вершина <tex> w </tex>, которая тоже является предком вершин <tex> u </tex> и <tex> v </tex>, и из которой мы вышли раньше во время обхода в глубину. Но тогда ситуация, что одна из вершин посещена, а у другой рассмотрены все дети, должна была выполниться раньше, и в качестве ответа должна была вернуться вершина <tex> w </tex>.
'''Замечание:''' для корректности алгоритма достаточно было бы одного массива <tex> dsu </tex>, а представителем класса всегда выбирать наименьшего общего предка вершин класса. Это несложно сделать, так как мы всегда объединяем ребёнка со своим родителем. Но в таком случае алгорим алгоритм получился бы менее эффективным, потому что одна только эвристика сжатия путей работает недостаточно быстро.
== Оценка сложности ==
Следовательно, итоговая асимптотика {{---}} <tex>O (n + m)</tex>, что при достаточно больших <tex>m</tex> составляет <tex>O (1)</tex> на один запрос.
==См. также==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Heavy-light декомпозиция]]
== Источники информации ==
