Где применяется
1. Задача
Служба поддержки постепенно узнаёт, что некоторые аккаунты принадлежат одному человеку. У двух аккаунтов один и тот же подтверждённый email, значит, это один человек. Номер телефона привязывает к ним третий аккаунт. Сотрудник поддержки вручную объединяет четвёртый. Такие факты приходят по одному и в любом порядке.
В любой момент кто-то может спросить: аккаунты A и B принадлежат одному человеку? Можно каждый раз заново строить всю карту «кто с кем связан». Но и факты, и вопросы идут непрерывным потоком, и полная пересборка на каждый вопрос быстро становится слишком медленной.
Нужны две операции, которые остаются быстрыми при любом числе слияний: объединить два аккаунта в одну группу и проверить, лежат ли два аккаунта уже в одной группе.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитunions [0, 1], [2, 3], [1, 3], [4, 5], [5, 6], [6, 3], [5, 1] on new UnionFind(7)7 элементов, каждый сам себе группа: каждый parent указывает на себя. Выполним 7 вызовов union.
Столбики: сколько раз посетили каждую вершину.
Одна операция: одна посещённая вершина, одно пройденное или добавленное ребро. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(q·(n + m))O(q·α(n))
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- лежат ли эти двое в одной группе
- факты о слиянии приходят по одному
- связность меняется по мере добавления рёбер
- склейка аккаунтов или друзей во времени
- это ребро замкнёт цикл
Похоже, но не то
- Компоненты связности (Connected components)
Заливка считает группы в уже готовом графе. Здесь ответ нужен, пока рёбра ещё приходят.
- Обход графа в ширину и глубину (Graph BFS / DFS)
Обход ходит по соседям, значит нужен список смежности. Здесь рёбра не хранятся совсем.
- Топологическая сортировка (Topological sort (Kahn's algorithm))
Топологический порядок требует направленных рёбер без циклов. Здесь любое ребро ненаправленное.
- Хеш-таблица и множество (Hash set / map)
Словарь группирует по заранее известному ключу. Здесь группы выясняются по мере слияний.
n до 1e6 элементов и m перемешанных запросов дают O(m alpha(n)). Alpha меньше 5 при любом реальном n.
На LeetCode
Задачи, где связи приходят по одной и всё время нужно знать, в одной ли группе два элемента. Union-find со сжатием путей отвечает на find и union почти за O(1).
Объединяй рёбра по порядку, и первое ребро, у которого оба конца уже с общим корнем, и есть ответ.
Объедини каждую пару, связанную через ==, потом проверь, что ни одна пара с != не имеет общего корня.
Пример из урока, где аккаунты с общей почтой объединяются, а каждый корень собирает свои адреса.
Объединяй камни с общей строкой или общим столбцом, и ответ равен числу камней минус число групп.