E114. Disjoint set union
Источник: e-maxx.ru/algo, страница PDF 358.
В данной статье рассматривается структура данных "Disjoint set union" (на английском "disjoint-set-union", или просто "DSU"). Эта структура данных предоставляет следующие возможности. Изначально имеется несколько elementов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно объединить два каких-либо множества, а также можно запросить, в каком множестве сейчас находится указанный element. Также, в классическом варианте, вводится ещё одна операция — создание нового elementа, который помещается в отдельное множество. Таким образом, базовый интерфейс данной структуры данных состоит всего из трёх операций:
●
— добавляет новый element
, помещая его в новое множество, состоящее из одного него.
●
— объединяет два указанных множества (множество, в котором находится element
,
и множество, в котором находится element
).
●
— returns, в каком множестве находится указанный element
. На самом деле
при этом returnsся один из elementов множества (называемый представителем или лидером (в англоязычной литературе "leader")). Этот представитель выбирается в каждом множестве самой структурой данных
(и может меняться с течением времени, а именно, после вызовов
).
НаVí dụ, если вызов
для каких-то двух elementов вернул одно и то же значение, то это означает, что эти elementы находятся в одном и том же множестве, а в противном случае — в разных множествах. Описываемая ниже структура данных позволяет делать каждую из этих операций почти за
в среднем
(более подробно об асимптотике см. ниже после описания Thuật toánа). Также в одном из подразделов статьи описан альтернативный вариант реализации DSU, позволяющий
добиться асимптотики
в среднем на один запрос при
; а при
(т.е.
значительно
больше
) — и вовсе времени
в среднем на запрос (см. "Хранение DSU в виде явного списка множеств").
Построение эффективной структуры данных
Определимся сначала, в каком виде мы будем хранить всю информацию. Множества elementов мы будем хранить в виде деревьев: одно cây соответствует одному множеству. Корень дерева — это представитель (лидер) множества.
При реализации это означает, что мы заводим mảng
, в котором для каждого elementа мы храним ссылку на
его предка в дерева. Для корней деревьев будем считать, что их предок — они сами (т.е. ссылка зацикливается в этом месте).
Наивная Cài đặt
Мы уже можем написать первую реализацию системы непересекающихся множеств. Она будет довольно неэффективной, но затем мы улучшим её с помощью двух приёмов, получив в итоге почти константное Thời gian chạy. Итак, вся информация о множествах elementов хранится у нас с помощью mảngа .
Чтобы создать новый element (операция
), мы просто создаём cây с корнем в вершине
,
отмечая, что её предок — это она сама.
Чтобы объединить два множества (операция
), мы сначала найдём лидеров множества, в
котором находится
, и множества, в котором находится
. Если лидеры совпали, то ничего не делаем — это значит,
что множества и так уже были объединены. В противном случае можно просто указать, что предок вершины
равен
(или наоборот) — тем самым присоединив одно cây к другому.
Наконец, Cài đặt операции поиска лидера (
) проста: мы поднимаемся по предкам от вершины
,
пока не дойдём до корня, т.е. пока ссылка на предка не ведёт в себя. Эту операцию удобнее реализовать рекурсивно (особенно это будет удобно позже, в связи с добавляемыми оптимизациями).
void make_set (int v) {
parent[v] = v;
}
int find_set (int v) {if (v == parent[v])return v;return find_set (parent[v]);}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b)parent[b] = a;
} Впрочем, такая Cài đặt системы непересекающихся множеств весьма неэффективна. Легко построить Ví dụ, когда после нескольких объединений множеств получится ситуация, что множество — это cây,
выродившееся в длинную цепочку. В результате каждый вызов
будет работать на таком тесте за
время порядка глубины дерева, т.е. за
. Это весьма далеко от той асимптотики, которую мы собирались получить (константное Thời gian chạy). Поэтому рассмотрим две оптимизации, которые позволят (даже применённые по отдельности) значительно ускорить работу.
Эвристика сжатия пути
Эта эвристика предназначена для ускорения работы
.
Она заключается в том, что когда после вызова
мы найдём искомого лидера
множества, то
запомним, что у вершины
и всех пройденных по пути вершин — именно этот лидер
. Проще всего это
сделать, перенаправив их
на эту вершину
.
Таким образом, у mảngа предков
смысл несколько меняется: теперь это сжатый mảng
предков, т.е. для каждой вершины там может храниться не непосредственный предок, а предок предка, предок предка предка, и т.д. С другой стороны, понятно, что нельзя сделать, чтобы эти указатели
всегда указывали на лидера: иначе
при выполнении операции
пришлось бы обновлять лидеров у
elementов.
Таким образом, к mảngу
следует подходить именно как к mảngу предков, возможно, частично сжатому.
Новая Cài đặt операции
выглядит следующим образом:
int find_set (int v) {if (v == parent[v])return v;return parent[v] = find_set (parent[v]);} Такая простая Cài đặt делает всё, что задумывалось: сначала путём рекурсивных вызовов находится лидера множества, а затем, в процессе раскрутки стека, этот лидер присваивается ссылкам
для
всех пройденных elementов. Реализовать эту операцию можно и нерекурсивно, но тогда придётся осуществлять два прохода по дереву: первый найдёт искомого лидера, второй — проставит его всем vertexм пути. Впрочем, на практике нерекурсивная Cài đặt не даёт существенного выигрыша.
Оценка асимптотики при применении эвристики сжатия пути
Покажем, что применение одной эвристики сжатия пути позволяет достичь логарифмическую асимптотику: на один запрос в среднем.
Заметим, что, поскольку операция
представляет из себя два вызова операции
и ещё
операций, то мы можем сосредоточиться в доказательстве только на оценку времени работы
операций
.
Назовём весом
вершины
number потомков этой вершины (включая её саму). Веса вершин, очевидно, могут только увеличиваться в процессе работы Thuật toánа.
Назовём размахом ребра
разность весов концов этого ребра:
(очевидно, у
вершины-предка вес всегда больше, чем у вершины-потомка). Можно заметить, что размах какого-либо
фиксированного ребра
может только увеличиваться в процессе работы Thuật toánа. Кроме того, разобьём рёбра на классы: будем говорить, что edge имеет класс
, если его размах
принадлежит отрезку
. Таким образом, класс ребра — это number от
до
.
Зафиксируем теперь произвольную вершину
и будем следить, как меняется edge в её предка: сначала оно
отсутствует (пока vertex
является лидером), затем проводится edge из
в какую-то вершину (когда множество
с вершиной
присоединяется к другому множеству), и затем может меняться при сжатии путей в процессе
вызовов
. Понятно, что нас интересует Asymptotic complexity только последнего случая (при сжатии путей):
все остальные случаи требуют
времени на один запрос.
Рассмотрим работу некоторого вызова операции
: он проходит в дереве вдоль некоторого пути, стирая
все рёбра этого пути и перенаправляя их в лидера. Рассмотрим этот путь и исключим из рассмотрения последнее edge каждого класса (т.е. не более чем по
одному ребру из класса
). Тем самым мы исключили
рёбер из каждого запроса. Рассмотрим теперь все остальные рёбра этого пути. Для каждого такого ребра, если оно имеет класс
,
получается, что в этом пути есть ещё одно edge класса
(иначе мы были бы обязаны исключить текущее edge,
как единственного представителя класса
). Таким образом, после сжатия пути это edge заменится на edge класса
как минимум
. given, что уменьшаться вес ребра не может, мы получаем, что для каждой вершины,
затронутой запросом
, edge в её предка либо было исключено, либо строго увеличило свой класс.
Отсюда мы окончательно получаем асимптотику работы
запросов:
, что (при
) означает логарифмическое Thời gian chạy на один запрос в среднем.
Эвристика объединения по рангу
Рассмотрим здесь другую эвристику, которая сама по себе способна ускорить Thời gian chạy Thuật toánа, а в сочетании с эвристикой сжатия путей и вовсе способна достигнуть практически константного времени работы на один запрос в среднем.
Эта эвристика заключается в небольшом изменении работы
: если в наивной реализации то, какое
cây будет присоединено к какому, определяется случайно, то теперь мы будем это делать на основе рангов. Есть два варианта ранговой эвристики: в одном варианте рангом дерева называется количество вершин в нём, в другом — глубина дерева (точнее, верхняя граница на глубину дерева, поскольку при совместном применении эвристики сжатия путей реальная глубина дерева может уменьшаться).
В обоих вариантах суть эвристики одна и та же: при выполнении
будем присоединять cây с
меньшим рангом к дереву с большим рангом. Приведём реализацию ранговой эвристики на основе размеров деревьев:
void make_set (int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {if (size[a] < size[b])swap (a, b);
parent[b] = a;
size[a] += size[b];
} } Приведём реализацию ранговой эвристики на основе глубины деревьев:
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {if (rank[a] < rank[b])swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])++rank[a];
} } Оба варианта ранговой эвристики являются эквивалентными с точки зрения асимптотики, поэтому на практике можно применять любую из них.
Оценка асимптотики при применении ранговой эвристики
Покажем, что Asymptotic complexity работы системы непересекающихся множеств при использовании только ранговой эвристики, без эвристики сжатия путей, будет логарифмической на один запрос в среднем: . Здесь мы покажем, что при любом из двух вариантов ранговой эвристики глубина каждого дерева будет
величиной
, что автоматически будет означать логарифмическую асимптотику для запроса
,
и, следовательно, запроса
. Рассмотрим ранговую эвристику по глубине дерева. Покажем, что если ранг дерева равен
, то
это cây содержит как минимум
вершин (отсюда будет автоматически следовать, что ранг, а, значит, и
глубина дерева, есть величина
). Доказывать будем по индукции: для
это очевидно. При сжатии
путей глубина может только уменьшиться. Ранг дерева увеличивается с
до
, когда к нему присоединяется
cây ранга
; применяя к этим двум деревьям размера
предположение индукции, получаем, что
новое cây ранга
действительно будет иметь как минимум
вершин, что и требовалось доказать. Рассмотрим теперь ранговую эвристику по размерам деревьев. Покажем, что если размер
дерева равен
, то его высота не более
. Доказывать будем по индукции: для
утверждение верно. При сжатии путей глубина может только уменьшиться, поэтому сжатие путей ничего не нарушает. Пусть
теперь объединяются два дерева размеров
и
; тогда по предположению индукции их высоты меньше либо
равны, соответственно,
и
. Не теряя общности, считаем, что первое cây — большее
(
), поэтому после объединения глубина получившегося дерева из
вершин станет равна: Чтобы завершить Chứng minh, надо показать, что:
что есть почти очевидное неравенство, поскольку
и
.
Объединение эвристик: сжатие пути плюс ранговая эвристика
Как уже упоминалось выше, совместное применение этих эвристик даёт особенно наилучший результат, в итоге достигая практически константного времени работы. Мы не будем приводить здесь доказательства асимптотики, поскольку оно весьма объёмно (см., наVí dụ, Кормен, Лейзерсон, Ривест, Штайн "Thuật toánы. Построение и анализ"). Впервые это Chứng minh было проведено Тарьяном (1975 г.). Окончательный результат таков: при совместном применении эвристик сжатия пути и объединения по рангу время
работы на один запрос получается
в среднем, где
— обратная функция
Аккермана, которая растёт очень медленно, настолько медленно, что для всех разумных ограничений
она
не превосходит 4 (Ví dụно для
). Именно поэтому про асимптотику работы системы непересекающихся множеств уместно говорить "почти константное Thời gian chạy".
Приведём здесь итоговую реализацию системы непересекающихся
множеств, реализующую обе указанные эвристики (используется ранговая эвристика относительно глубин деревьев):
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
int find_set (int v) {if (v == parent[v])return v;return parent[v] = find_set (parent[v]);}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {if (rank[a] < rank[b])swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])++rank[a];
} }
Applications в Bài toánх и различных улучшения
В этом разделе мы рассмотрим несколько применений структуры данных "Disjoint set union", как тривиальных, так и использующих некоторые улучшения структуры данных.
Поддержка компонент связности đồ thịа
Это одно из очевидных приложений структуры данных "Disjoint set union", которое, по всей видимости, и стимулировало изучение этой структуры. Формально задачу можно сформулировать таким образом: изначально дан пустой đồ thị, постепенно в этот đồ thị могут добавляться вершины и неориентированные рёбра, а также поступают запросы
— "в одинаковых
ли компонентах связности лежат вершины
и
?". Непосредственно применяя здесь описанную выше структуру данных, мы получаем Lời giải, которое обрабатывает один запрос на добавление вершины/ребра или запрос на проверку двух вершин — за почти константное время в среднем. given, что практически в точности такая же Bài toán ставится при использовании Thuật toánа Крускала нахождения минимального остовного дерева, мы сразу же получаем улучшенную версию этого Thuật toánа, работающую практически за линейное время. Иногда на практике встречается инвертированная версия этой задачи: изначально есть đồ thị с какими- то vertexми и рёбрами, и поступают запросы на удаление рёбер. Если Bài toán дана в оффлайн, т.е. мы заранее можем узнать все запросы, то решать эту задачу можно следующим образом: перевернём задачу задом наперёд: будем считать, что у нас есть пустой đồ thị, в который могут добавляться рёбра (сначала добавим edge последнего запроса, затем предпоследнего, и т.д.). Тем самым в результате инвертирования этой задачи мы пришли к обычной задаче, Lời giải которой описывалось выше.
Connected components на изображении
Одно из лежащих на поверхности применений DSU заключается в решении следующей задачи: имеется
изображение
пикселей. Изначально всё изображение белое, но затем на нём рисуется несколько чёрных пикселей. it is required определить размер каждой "белой" компоненты связности на итоговом изображении. Для решения мы просто перебираем все белые клетки изображения, для каждой клетки перебираем её четырёх соседей,
и если сосед тоже белый — то вызываем
от этих двух вершин. Таким образом, у нас будет DSU с
vertexми, соответствующими пикселям изображения. Получившиеся в итоге деревья DSU — и есть искомые компоненты связности. Впрочем, такое Lời giải с помощью системы непересекающихся множеств не имеет никаких преимуществ перед Lời giảiм с помощью обхода в глубину.
Поддержка дополнительной информации для каждого множества
"Disjoint set union" позволяет легко хранить любую дополнительную информацию, относящуюся ко множествам. Простой Ví dụ — это размеры множеств: как их хранить, было описано при описании ранговой эвристики (информация там записывалась для текущего лидера множества). Таким образом, вместе с лидером каждого множества можно хранить любую дополнительную требуемую в конкретной задаче информацию.
Применение DSU для сжатия "прыжков" по отрезку. Bài toán о
покраске подотрезков в оффлайне
Одно из распространённых применений DSU заключается в том, что если есть набор elementов, и из каждого elementа Đầu raит по одному ребру, то мы можем быстро (за почти константное время) находить конечную точку, в которую мы попадём, если будем двигаться вдоль рёбер из заданной начальной точки. Наглядным Ví dụом этого Applications является Bài toán о покраске подотрезков: есть отрезок длины
, каждая клетка которого (т.е. каждый кусочек длины
) имеет нулевой цвет. Поступают запросы вида
— перекрасить отрезок
в цвет
. it is required find итоговый цвет каждой клетки. Запросы считаются известными заранее, т.е. Bài toán — в оффлайне. Для решения мы можем завести DSU-структуру, которая для каждой клетки будет хранить ссылку на ближайшую справа непокрашенную клетку. Таким образом, изначально каждая клетка указывает на саму себя, а после покраски первого подотрезка — клетка перед началом подотрезка будет указывать на клетку после конца подотрезка. Теперь, чтобы решить задачу, мы рассматриваем запросы перекраски в обратном порядке: от последнего к первому. Для выполнения запроса мы просто каждый раз с помощью нашего DSU находим самую левую непокрашенную клетку внутри отрезка, перекрашиваем её, и перебрасываем указатель из неё на следующую справа пустую клетку. Таким образом, мы здесь фактически используем DSU с эвристикой сжатия путей, но без ранговой эвристики (т.к. нам важно, кто станет лидером после объединения). Следовательно, итоговая Asymptotic complexity составит
на
запрос (впрочем, с маленькой по сравнению с другими структурами данных константой). Cài đặt:
void init() {
for (int i=0; i<L; ++i)make_set (i);
}
void process_query (int l, int r, int c) {
for (int v=l; ; ) {v = find_set (v);
if (v >= r) break;answer[v] = c;
...
C# lời giải
bản nháp tự động, xem lại trước khi gửiusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
void make_set (int v) {
parent[v] = v;
}
int find_set (int v) {
if (v == parent[v])
return v;
return find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b)
parent[b] = a;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void make_set (int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (size[a] < size[b])
swap (a, b);
parent[b] = a;
size[a] += size[b];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void init() {
for (int i=0; i<L; ++i)
make_set (i);
}
void process_query (int l, int r, int c) {
for (int v=l; ; ) {
v = find_set (v);
if (v >= r) break;
answer[v] = c;
parent[v] = v+1;
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int len = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second += len;
}
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a) .first;
b = find_set (b) .first;
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, 1);
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int parity = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second ^= parity;
}
return parent[v];
}
void add_edge (int a, int b) {
pair<int,int> pa = find_set (a);
a = pa.first;
int x = pa.second;
pair<int,int> pb = find_set (b);
b = pb.first;
int y = pb.second;
if (a == b) {
if (x == y)
bipartite[a] = false;
}
else {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, x ^ y ^ 1);
if (rank[a] == rank[b])
++rank[a];
}
}
bool is_bipartite (int v) {
return bipartite[ find_set(v) .first ];
}
List<int> lst[MAXN];
int parent[MAXN];
void make_set (int v) {
lst[v] = List<int> (1, v);
parent[v] = v;
}
int find_set (int v) {
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (lst[a].size() < lst[b].size())
swap (a, b);
while (!lst[b].empty()) {
int v = lst[b].back();
lst[b].pop_back();
parent[v] = a;
lst[a].push_back (v);
}
}
}
}C++ lời giải
đã khớp/gốcvoid make_set (int v) {
parent[v] = v;
}
int find_set (int v) {
if (v == parent[v])
return v;
return find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b)
parent[b] = a;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void make_set (int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (size[a] < size[b])
swap (a, b);
parent[b] = a;
size[a] += size[b];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void init() {
for (int i=0; i<L; ++i)
make_set (i);
}
void process_query (int l, int r, int c) {
for (int v=l; ; ) {
v = find_set (v);
if (v >= r) break;
answer[v] = c;
parent[v] = v+1;
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int len = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second += len;
}
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a) .first;
b = find_set (b) .first;
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, 1);
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int parity = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second ^= parity;
}
return parent[v];
}
void add_edge (int a, int b) {
pair<int,int> pa = find_set (a);
a = pa.first;
int x = pa.second;
pair<int,int> pb = find_set (b);
b = pb.first;
int y = pb.second;
if (a == b) {
if (x == y)
bipartite[a] = false;
}
else {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, x ^ y ^ 1);
if (rank[a] == rank[b])
++rank[a];
}
}
bool is_bipartite (int v) {
return bipartite[ find_set(v) .first ];
}
vector<int> lst[MAXN];
int parent[MAXN];
void make_set (int v) {
lst[v] = vector<int> (1, v);
parent[v] = v;
}
int find_set (int v) {
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (lst[a].size() < lst[b].size())
swap (a, b);
while (!lst[b].empty()) {
int v = lst[b].back();
lst[b].pop_back();
parent[v] = a;
lst[a].push_back (v);
}
}
}Java lời giải
bản nháp tự động, xem lại trước khi gửiimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
void make_set (int v) {
parent[v] = v;
}
int find_set (int v) {
if (v == parent[v])
return v;
return find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b)
parent[b] = a;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void make_set (int v) {
parent[v] = v;
size[v] = 1;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (size[a] < size[b])
swap (a, b);
parent[b] = a;
size[a] += size[b];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
}
int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
void init() {
for (int i=0; i<L; ++i)
make_set (i);
}
void process_query (int l, int r, int c) {
for (int v=l; ; ) {
v = find_set (v);
if (v >= r) break;
answer[v] = c;
parent[v] = v+1;
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int len = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second += len;
}
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a) .first;
b = find_set (b) .first;
if (a != b) {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, 1);
if (rank[a] == rank[b])
++rank[a];
}
}
void make_set (int v) {
parent[v] = make_pair (v, 0);
rank[v] = 0;
bipartite[v] = true;
}
pair<int,int> find_set (int v) {
if (v != parent[v].first) {
int parity = parent[v].second;
parent[v] = find_set (parent[v].first);
parent[v].second ^= parity;
}
return parent[v];
}
void add_edge (int a, int b) {
pair<int,int> pa = find_set (a);
a = pa.first;
int x = pa.second;
pair<int,int> pb = find_set (b);
b = pb.first;
int y = pb.second;
if (a == b) {
if (x == y)
bipartite[a] = false;
}
else {
if (rank[a] < rank[b])
swap (a, b);
parent[b] = make_pair (a, x ^ y ^ 1);
if (rank[a] == rank[b])
++rank[a];
}
}
boolean is_bipartite (int v) {
return bipartite[ find_set(v) .first ];
}
ArrayList<Integer> lst[MAXN];
int parent[MAXN];
void make_set (int v) {
lst[v] = ArrayList<Integer> (1, v);
parent[v] = v;
}
int find_set (int v) {
return parent[v];
}
void union_sets (int a, int b) {
a = find_set (a);
b = find_set (b);
if (a != b) {
if (lst[a].size() < lst[b].size())
swap (a, b);
while (!lst[b].empty()) {
int v = lst[b].back();
lst[b].pop_back();
parent[v] = a;
lst[a].push_back (v);
}
}
}
}Материал разбит как Thuật toánическая Bài toán: изучить постановку, понять асимптотику и реализовать Thuật toán на выбранном языке.
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.