DSU со сжатием путей
Находите и объединяйте множества почти за константное время
«DSU со сжатием путей» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что отслеживает DSU
DSU объединяет элементы в непересекающиеся множества, поэтому с его помощью можно проверить, принадлежат ли два объекта одной группе. 🤝
Множества как деревья
DSU хранит каждое множество в виде дерева. Каждый элемент указывает на родителя, а узел на самом верху, корень, является уникальным именем всей группы.
Массив родителей
Все эти связи хранятся в одном массиве. Сначала каждый элемент является собственным родителем, то есть каждый объект начинает в отдельном множестве.
parent = list(range(n))Поиск корня
Операция find поднимается по связям с родителями, пока элемент не начинает указывать на самого себя. Этот указывающий на себя узел и есть корень, который обозначает множество.
while parent[x] != x:
x = parent[x]Длинные цепочки замедляют работу
Без специальных мер множества могут превращаться в длинные вытянутые цепочки. Тогда find проходит узлы один за другим, и один запрос может стоить O(n), что слишком медленно.
Сжатие путей
Сжатие путей решает эту проблему: во время поиска корня Вы направляете каждый посещённый узел прямо к корню, уплощая дерево для следующего раза. ⚡
Рекурсивное сжатие
Проще всего сделать это рекурсивно. Найдите корень, а затем сохраните его в parent[x] перед возвратом, чтобы связь навсегда стала короче.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Два элемента в одном множестве?
Чтобы проверить, связаны ли два элемента, сравните их корни. Если find(a) равен find(b), они находятся в одной группе; иначе они по-прежнему разделены.
if find(a) == find(b):
print("connected")Объединение двух множеств
Операция union объединяет группы, направляя один корень на другой. Одной строкой можно связать два целых дерева в одно множество.
def union(a, b):
parent[find(a)] = find(b)Почему это так быстро
Только со сжатием путей операции выполняются примерно за O(log n) амортизированного времени, а вместе с ранжированием достигают почти постоянного времени на запрос.
Где особенно полезен DSU
DSU решает задачи на связность: задачи о кругах друзей, компонентах сети и остовном дереве Крускала используют быстрые find и union. 🌐
Быстрая проверка
Подумайте, что именно меняет сжатие путей.
Повторение
Вы создали DSU: массив родителей, find для получения корня и union для объединения. Сжатие путей сохраняет молниеносную скорость работы. Отличная работа! 🎉
Часто задаваемые вопросы
Урок «DSU со сжатием путей» бесплатный?
Да — полный текст урока «DSU со сжатием путей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «DSU со сжатием путей»?
Находите и объединяйте множества почти за константное время Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «DSU со сжатием путей»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- DSU со сжатием путей
- Объединение по рангу и компоненты
- Минимальное остовное дерево Краскала
- MST Прима с кучей