3622
правки
Изменения
→Корректность
== Корректность ==
Случай, когда <tex> u </tex> является наименьшим общим предком вершин <tex> u </tex> и <tex> v </tex> отработает правильно, потому что по алгоритму в этот момент <tex> ancestor[\mathrm{find}(u)] = u </tex>.
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее {{---}} на минимальном предке.
Если он не минимальный, значит, есть на какой-то большей глубине, то есть такая вершина, которая была посещена раньше и для которой условия на <tex>u</tex> и <tex>v</tex> выполнялись, значит, тогда должна была найтись эта вершина в качестве <tex>LCA</tex>.
