\Section{Система непересекающихся множеств}{4 декабря}{Глеб Винерский}


\Subsection{Система непересекающихся множеств}
 

\Subsubsection{Определение}

СНМ - Система непересекающихся множеств

DSU - Disjoint Set Union
\\

СНМ - это структура данных, поддерживающая две операции:

int get(int v) - получить номер множества, которому принадлежит элемент $v$

void join(int u, int v) - объединить множества, в которых лежат элементы $u$ и $v$

Также часто бывает полезной is(u,v): \{get(u)==get(v)\}, проверяющая элементы u,v на принадлежность одному множеству.
 
\Subsubsection{СНМ на списках}

color[v] - номер множества, которому принадлежит v

list[col] - вершины множества под номером col

get:  return  color[v] $\O(1)$

join: if color[u] != color[v]: merge(list[color[u]], list[color[v]])

merge: 1)Перекрасим вершины меньшего множества.

~~~~~~~~~~2)Объединим списки.

Здесь мы пользуемся уже знакомым приемом присоединения меньшего множества к большему, благодаря которому каждый элемент будет перекрашен не более $\log n$ раз. Таким образом асимптотика последовательного объединения $n$ одноэлементных множеств в одно $\O(n\log n)$.
 
\Subsubsection{СНМ на деревьях}

Давайте хранить множества в виде деревьев. Корень каждого дерева - какой-то элемент множества, выполняющий роль его идентификатора.

parent[v] - предок элемента $v$

parent[root] = root

join(u,v): p[get(u)]=get(v)

get(v): return v == p[v] ? v : get(p[v])

Время: join=$1+2\cdot get$, get=$\O(n)$

\Subsection{Эвристики}
 
\Subsubsection{Сжатие путей}

Каждый раз когда вызывается get будем переподвешивать к корню все вершины на пути между ним и $v$.

get(v): return v == p[v] ? v : (p[v] = get(p[v]))
 
\begin{Thm}
	Сложность $m$ join'ов из $n$ одноэлементных множеств с эвристикой сжатия путей равна $(m+n)\log n$
	\begin{proof}
		Назовем легкими ребра $ab$(ребра направлены вверх по дереву), для которых $size[a]<\frac{1}{2}size[b]$, соответственно тяжелыми будут ребра, для которых $size[a]\ge \frac{1}{2}size[b]$. 

За один get мы пройдём не более $\log n$ легких ребер. Всего $m\log n$ легких ребер во всех запросах.

Теперь оценим количество тяжелых ребер. Так как эвристика сжатия путей переподвешивает вершины к корню, то мы будем удалять все пройденные ребра. Так как у каждой вершины можно удалить тяжелое ребро не более $\log n$ раз, то всего мы обработаем не более $n\log n$ тяжелых ребер. 

$m\log n + n\log n = (m+n)\log n$
	\end{proof}
\end{Thm}

\Subsubsection{Ранговая}

Храним для каждого дерева его размер. При объединении меньшее дерево подвешивается к большему. Соответственно $depth\le \log n$, $size[depth] \ge 2^{depth}$.

Вместо размеров можно хранить "ранги" деревьев. Изначально ранги всех одноэлементных деревьев равны 0. При объединении дерево меньшего ранга подвешивается к дереву большего ранга, а при равенстве порядок объединения произвольный, и ранг получившегося дерева увеличивается на 1. 

$rank[v] \le \log n$

$size[rank] \ge 2^{rank}$

 Ранги требуют $\log$ памяти, которая нужна на хранение размеров.

Стоит упомянуть реализацию $join$, подвешивающую деревья в случайном порядке. Такая реализация дает лишь константное ускорение работы примерно в 2 раза.
