Изменения
→Проблема наивной реализации
== Проблема наивной реализации ==
[[Файл:ve.png|thumb|400px|Реализация без весовой эвристики]]
Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списков списка будем хранить указатель на представителя и на следующий элемент в списке.
При такой реализации операция init для создания n множеств из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
