СНМ

Содержание

1 Задача:
2 Лемма о ранговой эвристике

Задача:

Хотим реализовать структуру данных, которах поддерживает следующие операции:

$init(n)$: создать $n$ независимых вершин, в каждой из которой записан свой номер, от $0$ до &n-1&
$Merge(i, j)$: объединить в одну компоненту связности компоненты связности, в которых сейчас лежат вершины $i$ и $j$
$GetComponentId(i)$: выдать идентификатор компоненты, в которой лежит вершина $i$. Разумеется, мы хотим, чтобы для всех вершин в одной компоненте ответ был одинаковый.

Реализуем эту структуру с помощью леса из корневых деревьев $~-$ каждая вершина будет знать своего предка в своём дереве, у вершины-корня положим предком её саму. Изначально (после $init$-а) все вершины будут являться деревом размера $1$.

Тогда, чтобы отвечать на $3$-ий запрос, нам достаточно возвращать корень дерева, в котором находится вершина $~-$ для этого надо подниматься в предка до тех пор, пока не дойдём до корня $~-$ у него предком будет он сам.

Чтобы реализовать $Merge(i, j)$, нам надо научиться объединять деревья. Вспомним, что в $GetComponentId$ нам нужно подниматься от вершины до корня. Значит, нам хотелось бы, чтобы эта величина была как можно меньше в среднем. Значит, надо следить за тем, чтобы деревья получались сбалансированными. Для этого будем хранить в каждой вершине $rank(i) ~-$ длину самого длинного пути от вершины вниз до листа. При $Merge(i, j)$ корневых деревьев у нас есть 2 варианта: подвесить $root(i)$ к $root(j)$ или наоборот. Выберем тот из вариантов, в котором получившееся дерево будет более сбалансированным. Для этого будем подвешивать вершину с меньшим рангом к вершине с большим, а при равенстве будем подвешивать первую вершину ко второй, увеличивая ранг второй на 1.

Talk is cheap. Show me the code

vector<int> p;
vector<int> rank;

void init(n) {
  p.resize(n);
  p.iota(p.begin(), p.end(), 0);
  /* equivalent to
   *
   * for (int i = 0; i < n; ++i) {
   *   p[i] = i;
   * }
   *
   */
  
  rank.resize(n, 0);
}

int GetRoot(int i) {
  while (p[i] != i) {
    i = p[i];
  }

  return i;
}

void Merge(int i, int j) {
  int root_i = GetRoot(i);
  int root_j = GetRoot(j);

  // если вершины лежат в одном дереве
  // то можно ничего не делать
  if (root_i == root_j) {
    return;  
  }

  if (rank[root_i] < rank[root_j]) {
    p[root_i] = root_j;
  } else if (rank[root_j] < rank[root_i]) {
    p[root_j] = root_i;
  } else {
    p[root_i] = root_j;
    rank[root_j]++;
  }
}

Лемма о ранговой эвристике

Если $rank(v) = r$, то в поддереве вершины $v$ хотя бы $2^v$ вершин.

Доказательство

Будем доказывать индукцией по $r$.

База

$r = 0$

Шаг

Дерево ранга $r$ мы получаем только при объединении двух деревьев ранга $r - 1$. В каждом из них, по предположению индукции, хотя бы $2^{r-1}$ вершин. Значит, в их объединении будет хотя бы $2^{r}$ вершин.

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex