Информатика · объяснение и практика
Как система непересекающихся множеств поддерживает компоненты связности
Проследите объединение компонент через корни деревьев: почему find сравнивает представителей, а не непосредственных родителей, и когда обычной DSU недостаточно.

В теме Графы и маршруты · Учебная карта
Главная мысль
Система непересекающихся множеств, или DSU, хранит разбиение объектов на группы. Find находит представителя группы, union объединяет две группы. Для постепенно добавляемых неориентированных связей это позволяет проверять, соединены ли два объекта какой-нибудь цепочкой.
Объединяются целые группы
Пусть в мастерской пять устройств с номерами от одного до пяти. Сначала каждое находится в собственной группе. После добавления связей 1—2 и 4—5 получаются две пары и одиночное устройство 3. Связь 2—4 объединяет обе пары целиком: теперь цепочкой соединены также устройства 1 и 5, хотя прямого кабеля между ними нет.
DSU не обязана хранить путь по исходной сети. В распространённом представлении у каждого объекта есть родитель, а корень дерева служит представителем группы. Родительский указатель означает принадлежность множеству, а не обязательно реальный кабель. Поэтому нельзя выдавать цепочку этих указателей за найденный физический маршрут или вычислять по ней расстояние между устройствами.
Сравниваются корни, а не ближайшие родители
Пусть родители заданы так: 1 указывает на 2, 2 на 4, а 4 является корнем. У устройства 5 непосредственный родитель тоже 4. Родители 1 и 5 различны, но find для обоих приводит к 4. Значит, объекты в одной группе. Проверка только первого указателя ошибочно объявила бы их разъединёнными.
При union сначала находят два корня. Если они одинаковы, разбиение не меняется и число компонент не уменьшается. Если различны, один корень присоединяют к другому. Для ограничения высоты маленькое дерево можно присоединять к большому. Сжатие путей дополнительно направляет посещённые вершины ближе к корню, сохраняя само разбиение.
Пример
Для объектов А, Б, В, Г выполнены union(А, Б), union(В, Г), затем union(Б, Г). Сколько групп осталось?
После двух операций были две группы по два объекта. Последняя операция соединила их представителей, поэтому осталась одна группа. Повтор union(А, В) уже не уменьшил бы это число.
Отметьте операции, которых структура не умеет делать
Обычная DSU удобно поддерживает слияния, но не произвольное удаление связи. Если убрать кабель 2—4, прежнее объединение не содержит достаточно сведений, чтобы автоматически восстановить две отдельные группы. Для такой задачи нужна перестройка по оставшимся связям или другой алгоритм. Аналогично направленная достижимость не сводится к симметричному отношению «в одной компоненте».
Представитель может измениться после объединения или оптимизации, хотя состав группы останется тем же. Если группе нужен постоянный внешний идентификатор, его хранят отдельно от технического корня. В ответе на учебную задачу удобно показывать именно множества объектов после каждого шага, а массив родителей использовать как способ реализации, не смешивая два уровня описания.
От чтения к действию
А теперь — вы
Частые вопросы
Если find вернул разные числа, группы обязательно различны?
Да, в корректно поддерживаемой DSU представитель един для каждой текущей группы. Сравнивать нужно результаты полного find, а не произвольные промежуточные указатели.
Почему повторное объединение может ничего не изменить?
Объекты уже могли быть связаны через другие элементы. После сравнения одинаковых корней число компонент остаётся прежним.
Углублённый разбор
Откат DSU решает связность с удалениями офлайн
Обычная DSU быстро объединяет компоненты, но не умеет удалять произвольное ребро. Если вся временная последовательность известна заранее, удаления можно превратить в интервалы жизни. Дерево времени и откат объединений позволяют ответить на каждый запрос в точном состоянии графа.
Перед началом: Система непересекающихся множеств; Дерево отрезков.
Удаление превращается в конец полуоткрытого интервала
Нумеруем события 0,…,Q−1 и считаем состояние сразу после события. Добавленное в l и удалённое в r ребро активно на [l,r); неудалённое живёт до Q. Фиксируем простой граф, где повторное добавление уже активного ребра и удаление отсутствующего не разрешены. Если нужны кратные экземпляры, потребуется отдельный учёт их идентификаторов или счётчиков, а не молчаливое объединение интервалов.
Каждый интервал раскладываем на O(log Q) узлов дерева отрезков. В узле хранятся рёбра, активные на всём его временном сегменте. На пути от корня к листу t оказываются ровно интервалы, содержащие t: каждый такой интервал покрывает лист одним своим каноническим узлом. Это свойство заменяет удаление в хронологическом онлайн-порядке.
Снимок стека делает объединения обратимыми
DSU использует объединение по размеру без сжатия путей. Перед изменением корня и размера сохраняем их прежние значения в стек. Снимок — текущая длина стека. Откат восстанавливает записи в обратном порядке до снимка. Безрезультатное объединение уже связанной пары может ничего не записывать, если откат привязан именно к длине стека, а не к числу попыток union.
Сжатие путей по умолчанию отключено: оно меняет много родителей при find и потребовало бы тоже журналировать все эти изменения, разрушая простую оценку. Объединение меньшего дерева с большим само по себе даёт глубину O(log n). Поэтому поиск корня и попытка union занимают O(log n), а восстановление каждой сохранённой ячейки — O(1). Откат не является новым разбиением по удаляемому ребру: он возвращает конкретный предшествующий снимок.
DFS по времени изолирует соседние ветви
При входе в узел сохраняем снимок и объединяем все его рёбра. Затем посещаем детей; в листе отвечаем на запрос текущей связности. При выходе откатываемся к снимку, поэтому изменения левой временной ветви не загрязняют правую. На каждом листе DSU соответствует в точности активным рёбрам этого времени, что доказывается индукцией по пути дерева. При O(Q) интервалах общая оценка O(Q log Q log n); метод требует офлайн-доступа ко всем событиям и не обещает немедленной обработки неизвестных будущих удалений.
Связность исчезает и возвращается по другому ребру
Условие. Для вершин A,B,C события таковы:0 добавить AB;1 спросить A,C;2 добавить BC;3 спросить A,C;4 удалить AB;5 спросить A,C;6 добавить AC;7 спросить A,B. Найдите интервалы и ответы.
- Ребро AB активно на[0,4), BC на[2,8), AC на[6,8). Эти интервалы раскладываются по узлам дерева времени; удаление в4 уже исключает AB из состояния листа 4.
- В листе 1 активно только AB, поэтому A и C не связаны. В листе 3 активны AB,BC, и все три вершины находятся в одной компоненте.
- В листе 5 осталось BC, так что A изолирована и ответ A,C снова отрицательный. В листе 7 рёбра BC,AC соединяют все вершины, поэтому A,B связаны.
- При переходе между ветвями дерево откатывает временные объединения к снимку. Нельзя оставить объединение AB после выхода из сегмента, где оно активно: это превратило бы третий ответ в ложное положительное.
Ответ. Ответы запросов во времена 1,3,5,7: нет,да,нет,да.
Проверка. Независимая хронологическая симуляция хранит актуальное множество рёбер и выполняет BFS при каждом запросе. Она даёт те же четыре ответа без использования DSU и дерева времени.
Где легко ошибиться. Не применяйте обычную DSU к удалению, просто убирая ребро из списка. Родительские связи DSU сохранят старую компоненту; нужен откат всей временной ветви либо другая структура динамической связности.
Проверьте понимание
Вопросы к этой главе
Почему интервалы полуоткрытые?
При соглашении «состояние после события» удаляемое в r ребро уже не активно в r. Запись[l,r) кодирует это без дополнительной поправки на один индекс и согласует добавление в l с немедленной активностью.
Нужно ли записывать каждую неудачную попытку union?
Не обязательно. Если снимок хранит длину журнала изменений, отсутствие изменений безопасно. Но если интерфейс откатывает ровно одну операцию, ему понадобится специальная запись о пустой попытке. Эти два соглашения нельзя смешивать.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- KACTL: UnionFindRollback.h, Polacek/Lindholm
Прочитан полный официальный исходник структуры с undo: find без сжатия, объединение по размеру, time/rollback и сохранение прежних ячеек. Структура источника — primary implementation; разложение интервалов жизни по дереву времени и доказательство для нашей временной шкалы изложены самостоятельно, не приписываются этому header.
DSU с потенциалами проверяет разности неизвестных
DSU может хранить не только принадлежность компоненте, но и разность неизвестных между вершиной и представителем. При сжатии пути эти потенциалы складываются. Новое уравнение либо связывает две компоненты с вычисленным сдвигом корней, либо проверяет уже определённую разность и обнаруживает противоречивый цикл.
Перед началом: Find и union в DSU; Аддитивные уравнения разностей.
Потенциал имеет направление и знак
Для каждой вершины v храним w[v]=x_v−x_parent[v]. У корня родитель он сам, вес нулевой. Find(v) должен вернуть корень r и P_v=x_v−x_r. Если путь содержит v→p→r, то P_v=w[v]+P_p. При сжатии родителя к r записываем именно эту сумму, а не прежний вес одного ребра.
Потенциал не является расстоянием в неотрицательной метрике: он может быть отрицательным, и смена направления меняет знак. Общий сдвиг всех x внутри компоненты не меняет разностей. Поэтому без дополнительного якорного уравнения структура не определяет абсолютные значения переменных.
Объединение выводится из исходного уравнения
Пусть добавляется x_v−x_u=d, корни равны r_u,r_v, а Find дал P_u,P_v. Если r_v прикрепляется к r_u, нужно записать w[r_v]=d+P_u−P_v. Действительно, x_v−x_u=P_v+(x_rv−x_ru)−P_u. Это тождество проверяет все три знака.
Если эвристика размера выбирает противоположное прикрепление, сдвиг корней нужно отрицать. Нельзя просто поменять номера корней, сохранив прежний вес. При уже общем корне объединять нечего: проверяется P_v−P_u=d. Неравенство означает несовместность добавленного ограничения с накопленными уравнениями.
Цикл ограничений создаёт независимое свидетельство
В согласованной компоненте сумма заданных разностей вдоль любого замкнутого ориентированного обхода равна нулю. Если новое уравнение замыкает цикл с ненулевой суммой, решения не существует. DSU обнаруживает это через разность потенциалов, но для объяснения ошибки полезно сохранить сами уравнения цикла.
При целых разностях все вычисления можно выполнять точно в целых достаточной длины. Для равенств с плавающей точкой понадобится отдельная модель допуска, иначе округления могут создать ложное противоречие. Удаление произвольного ограничения также не поддерживается обычным сжатием пути; это другая динамическая задача.
Сдвиг целой компоненты и несовместное пятое уравнение
Условие. Последовательно добавьте b−a=4,c−b=−2,d−e=3,d−c=5. Найдите все разности относительно a, затем проверьте e−a=5.
- Первые два равенства дают b=a+4,c=a+2. Отдельная компонента имеет d=e+3; её можно временно хранить с корнем e и весом d, равным трём.
- При соединении через d−c=5 получаем e−a=5+2−3=4. Поэтому корень e прикрепляется к a со сдвигом четыре.
- После сжатия пути d→e→a потенциал d складывается из 3+4=7. Итоговые потенциалы относительно a: a=0,b=4,c=2,d=7,e=4.
- Следовательно, e−b=0. Новое требование e−a=5 противоречит уже установленной разности четыре и должно быть отвергнуто.
- Сумма вдоль a→b→c→d→e равна 4−2+5−3=4. Добавленная обратная связь с требованием пять даёт ненулевую замкнутую сумму и независимо удостоверяет несовместность.
Ответ. Решения первых четырёх уравнений: (a,b,c,d,e)=(t,t+4,t+2,t+7,t+4). Пятое равенство несовместно; потенциал d после сжатия равен 7.
Проверка. Подстановка одного свободного параметра проверяет все четыре принятых равенства. Отдельная сумма разностей цикла доказывает отказ без доверия к массиву родителей.
Где легко ошибиться. Не сохраняйте старый вес d→e после замены родителя d на a. При сжатии меняется относительная опорная вершина, поэтому вес обязан превратиться из трёх в семь.
Проверьте понимание
Вопросы к этой главе
Почему нельзя получить численное значение a?
Все ограничения содержат только разности. Любое общее прибавление t ко всем переменным сохраняет систему, поэтому остаётся свободный общий сдвиг.
Что проверять при объединении уже связанных вершин?
Сравнить накопленную разность P_v−P_u с новой d. Повторное согласованное уравнение ничего не меняет, противоречивое создаёт отрицательный ответ, а не ещё одно объединение.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- CP-Algorithms project: DSU with accumulated distances
Прочитан раздел Support distances up to representative с обновлением добавочного веса при сжатии пути. Обобщение на знаковые разности, формула объединения и цикл несовместности выведены отдельно. Код проекта служит ссылкой на конкретный приём реализации, не источником абсолютных координат.
Тарьян отвечает офлайн-запросы ближайшего общего предка через DSU
Если все запросы ближайшего общего предка известны заранее, дерево можно обойти один раз, отвечая через структуру непересекающихся множеств. Важен не сам представитель DSU, а отдельная метка предка, которая обновляется после завершения каждого поддерева.
Перед началом: Обход дерева в глубину и порядок завершения; DSU: объединение множеств и поиск представителя.
Почему известные заранее запросы меняют алгоритм
В корневом дереве LCA(u, v) — общий предок, находящийся глубже остальных. Офлайн-постановка означает, что все пары известны до обхода. Каждый запрос сохраняют у обоих концов. Когда один конец обрабатывается, второй может ещё не быть завершён: в таком случае ответ откладывается. После завершения обоих концов результат можно получить без подъёма по дереву на каждый запрос.
Для вершины v создают отдельное множество DSU и метку ancestor[find(v)]=v. После возврата из ребёнка его множество объединяют с множеством v, затем метку нового представителя снова устанавливают равной v. Представитель после объединения по рангу может оказаться ребёнком или другой вершиной. Именно поэтому номер представителя нельзя автоматически объявлять ответом LCA.
Когда вершина становится готовой для запроса
После обработки всех детей вершину помечают завершённой. Для запроса (v, u), у которого u уже завершена, ответ равен ancestor[find(u)]. К этому времени множество u поднято объединениями до той активной части обхода, которая связывает обе вершины. Порядок «сначала обработать детей, потом отвечать» обеспечивает правильный результат и для пары, в которой один конец является предком другого.
При реализации нужно хранить идентификатор запроса, чтобы два его появления в списках концов не создали две противоречивые записи. Пара (v, v) имеет ответ v: отметка завершения ставится до просмотра запросов самой вершины. Для леса без общего искусственного корня запросы между разными компонентами требуют отдельного ответа «общего предка нет»; здесь рассматривается одно связное корневое дерево.
Сложность и проверяемый инвариант
При объединении по рангу и сжатии пути суммарная сложность составляет O((n+q)α(n)), где n — число вершин, q — число запросов. Нужно O(n+q) памяти для дерева, структуры DSU и списков пар. Это оценка целого пакетного расчёта, а не обещание того же метода для поступающих после обхода онлайн-запросов.
Полезный инвариант связывает метку с логической вершиной обхода, а не с внутренним устройством DSU. После объединения завершённого поддерева с родителем ancestor у представителя должен указывать на родителя. В тесте можно независимо получить LCA подъёмом по массиву родителей: такой медленный способ удобен для маленьких деревьев и не повторяет проверяемый механизм объединений.
Два запроса внутри ветви и между ветвями
Условие. Корень 0 имеет детей 1 и 2; у 1 дети 3 и 4; у 2 ребёнок 5. Обходите детей по возрастанию номера. Найдите LCA(3,4), LCA(3,5), LCA(2,5).
- После завершения 3 его множество объединяется с 1, метка представителя становится 1. При завершении 4 другой конец запроса(3,4) уже готов; метка find(3) равна 1.
- После полного завершения поддерева 1 его множество объединяется с 0 и получает метку 0.
- При завершении 5 запрос(3,5) видит завершённую 3. Её множество уже относится к обработанной ветви корня, и метка равна 0.
- Пока обрабатывается 5, вершина 2 ещё не завершена. Запрос(2,5) получает ответ при завершении 2 после объединения с 5: текущая метка равна 2.
Ответ. LCA(3,4)=1; LCA(3,5)=0; LCA(2,5)=2.
Проверка. Цепочки родителей:3→1→0,4→1→0,5→2→0. Их непосредственное пересечение подтверждает все три ответа независимо от порядка представителей DSU.
Где легко ошибиться. Не возвращайте find(u) вместо ancestor[find(u)]. Объединение по рангу выбирает удобный технический корень множества, который не обязан быть нужным предком дерева.
Проверьте понимание
Вопросы к этой главе
Можно ли убрать хранение запросов у обоих концов?
Можно, только если заранее обеспечить обработку пары после готовности нужного конца другим способом. Дублирование пары в двух списках — простой способ не пропустить подходящий момент обхода.
Зачем отдельно помечать завершённые вершины?
Одного факта посещения недостаточно: вершина ещё может быть активным предком в стеке обхода. Условие завершения согласует запрос с уже выполненными объединениями и доказанным инвариантом меток.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- MIT6.854J: офлайн-задача общего предка
Задача 4 описывает объединения в порядке завершения и отдельное имя представителя. Дерево из шести вершин и последовательность трёх ответов разобраны самостоятельно.
Дерево реконструкции Краскала отвечает на пороговые запросы связности
Обычная DSU отвечает, связаны ли вершины после уже выполненных объединений, но теряет момент их первого соединения. Если добавлять рёбра по неубыванию веса и при каждом успешном слиянии создавать отдельный узел истории, получится дерево реконструкции. Метка наименьшего общего предка двух исходных вершин равна минимальному порогу, при котором между ними появляется путь.
Перед началом: DSU и объединение компонент; Наименьший общий предок в корневом дереве.
Пороговый запрос минимизирует самое тяжёлое ребро пути
Конечный неориентированный граф с вещественными весами; пороговый подграф содержит рёбра веса не больше λ; запросы между различными вершинами.
Для пути P обозначим его узкое место как max w(e). Две разные вершины соединены в подграфе порога λ ровно тогда, когда существует путь с узким местом не больше λ. Следовательно, минимальный допустимый порог равен min_P max_e w(e). Это не сумма весов пути: длинный путь с лёгкими рёбрами может быть лучше короткого с одним тяжёлым.
Если исходные вершины находятся в разных компонентах всего графа, никакого конечного порога нет. Для запроса вершины к самой себе пустой путь требует отдельной договорённости; здесь рассматриваем только разные вершины, чтобы не назначать пустому максимуму произвольный вес.
Каждое успешное объединение создаёт новый узел истории
Сначала исходные вершины являются листьями отдельных деревьев. Сортируем рёбра по весу. Если концы уже принадлежат одной компоненте, история не меняется. Иначе создаём новый узел с меткой веса ребра и делаем корни двух объединяемых деревьев его детьми. Для новой DSU-компоненты сохраняем ссылку на этот узел.
После обработки всех рёбер с весом не больше λ листья под каждым уже образованным корнем соответствуют ровно одной компоненте порогового графа. Это следует из обычного инварианта DSU и не зависит от того, какие лишние внутренние рёбра были пропущены. Родительские указатели технической DSU и рёбра дерева истории при этом являются разными структурами.
Общий предок хранит значение, а не единственный путь
Для листьев u,v первый объединяющий их узел — их наименьший общий предок. Раньше его метки они находились в разных компонентах, а на этой метке уже соединены, что доказывает ответ. При равных весах бинарная форма дерева зависит от порядка обработки, но все затронутые метки равны; пороговые ответы остаются неизменными.
В связном графе создаётся n−1 внутренних узлов, всего 2n−1. В несвязном получается лес с меньшим числом слияний; искусственный общий корень нельзя выдавать за реальный конечный порог. После подготовки LCA множество парных запросов обрабатывается без повторного просмотра всех весов; сами исходные пути дерево истории автоматически не хранит.
Две разные истории слияний имеют одинаковые пороги
Условие. Вершины A,B,C,D,E,F и рёбра AB:2,CD:2,BC:5,DE:5,AE:8; вершина F изолирована. Найдите минимальные пороги для A,C и A,E, а также решите запрос A,F.
- При весе 2 создаём узлы X=(A,B) и Y=(C,D), оба с меткой 2. Вершины E и F пока отдельны.
- Сначала обрабатывая BC:5, получаем Z=(X,Y) с меткой 5, затем DE:5 создаёт W=(Z,E) с той же меткой. Ребро AE:8 уже внутреннее и нового узла не создаёт.
- Для A,C общий предок Z имеет метку 5. Для A,E общий предок W тоже имеет метку 5. Путь A—B—C—D—E использует веса 2,5,2,5 и достигает этого порога.
- Если поменять порядок двух рёбер веса 5, изменится форма промежуточных узлов, но обе пары по-прежнему соединятся на 5. Вершина F остаётся отдельным корнем леса, поэтому A,F не имеют конечного порога.
Ответ. Пороги A,C и A,E равны 5. Для A,F связности нет ни при каком конечном пороге.
Проверка. Независимый обход графов с порогами 2,5,8 показывает: на 2 компоненты AB,CD,E,F; на 5 все A,…,E соединены, F изолирована. Четыре успешных слияния дают 10 узлов леса из шести листьев.
Где легко ошибиться. Не используйте текущий технический корень DSU как историческую метку. Оптимизации find меняют родителей, поэтому историю порогов нужно сохранять в отдельном неизменяемом дереве слияний.
Проверьте понимание
Вопросы к этой главе
Равные веса делают ответ неоднозначным?
Неоднозначной может быть бинарная форма дерева. Значение порога не меняется, потому что все переставленные объединения происходят при одной и той же λ.
Почему ребро AE веса 8 не улучшает запрос A,E?
К моменту 8 уже существовал путь с максимальным ребром 5. Более короткая по числу рёбер прямая связь не уменьшает минимаксный порог.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sedgewick, Wayne — KruskalMST, конструктор
Первичный исходник: сортировка рёбер и объединение разных DSU-компонент, включая несвязный граф и равные веса. Дерево истории, LCA-критерий и пороговый пример выведены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Чем минимальное остовное дерево отличается от кратчайших путей
Сравните сумму веса сети с длиной маршрута от одной вершины: постройте минимальный остов на собственном примере и проверьте, почему цели различаются.
Открыть темуКогда список смежности выгоднее матрицы
Сравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.
Открыть тему