Объединение по рангу и компоненты
Делайте деревья плоскими и подсчитывайте группы
«Объединение по рангу и компоненты» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Операция union может быть простой
Обычная операция union просто подвешивает один корень под другой. При неосторожной реализации это может создать высокое медленное дерево, поэтому нужен более разумный способ объединять корни.
Главная идея
union по рангу всегда присоединяет короткое дерево к более высокому. Неглубокие деревья ускоряют все последующие операции find. 📏
Что означает ранг
Ранг — это оценка высоты дерева. Каждый элемент начинает с рангом 0, поскольку у отдельного узла нет глубины ниже него.
rank = [0] * nПрисоединяйте короткое дерево к высокому
Сравните ранги двух корней. Корень с меньшим рангом становится дочерним узлом, поэтому объединённое дерево остаётся как можно более плоским.
if rank[ra] < rank[rb]:
parent[ra] = rbПри равенстве увеличьте ранг
Если у обоих корней одинаковый ранг, выберите любой из них новым корнем и увеличьте его ранг на единицу, поскольку дерево стало на один уровень выше.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Вариант с объединением по размеру
Популярная альтернатива — union по размеру: присоединять меньшее множество к большему. Это столь же эффективно и позволяет бесплатно получать размеры групп.
Подсчёт компонент
Начните счётчик со значения n, поскольку каждый элемент является отдельной группой. Каждая успешная операция union объединяет две группы в одну, поэтому уменьшайте счётчик.
components = nПропускайте бесполезные операции union
Если два элемента уже имеют общий корень, операция union ничего не делает. Уменьшайте счётчик только тогда, когда их корни действительно различаются.
if find(a) != find(b):
union(a, b)
components -= 1Ранг плюс сжатие
Объедините union по рангу со сжатием путей — и DSU будет работать за обратное к функции Аккермана время, то есть практически за константное время для любых реальных входных данных. ⚡
Размеры групп по запросу
При объединении по размеру можно мгновенно узнать размер любой группы: достаточно прочитать размер, сохранённый в корне элемента.
group = size[find(x)]Где это применяется
Подсчёт компонент помогает отвечать на классические вопросы, например о количестве кругов общения или связных областей после последовательности операций объединения. 🌐
Быстрая проверка
Проанализируйте, как изменяется счётчик компонент.
Повторение
Вы изучили объединение по рангу, позволяющее сохранять деревья плоскими, а также научились отслеживать количество компонент и размеры групп. DSU теперь работает невероятно быстро! 🎉
Часто задаваемые вопросы
Урок «Объединение по рангу и компоненты» бесплатный?
Да — полный текст урока «Объединение по рангу и компоненты» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Объединение по рангу и компоненты»?
Делайте деревья плоскими и подсчитывайте группы Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Объединение по рангу и компоненты»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- DSU со сжатием путей
- Объединение по рангу и компоненты
- Минимальное остовное дерево Краскала
- MST Прима с кучей