DSU

Расшифровывается как “disjoint set union”, на русском говорят “система непересекающихся множеств” или СНМ.

Идея такова: пусть есть n элементов, каким-то образом разбитых на непересекающиеся множества. DCU это структура данных, реализующая запросы двух видов: объединить два множества и сказать, в каком множестве лежит какой-то элемент. Для реализации структуры представим все множества в виде деревьев. Для каждого элемента будем хранить его предка, а для корня дерева - его самого. Тогда для того, чтобы найти множество элемента - пройдемся по предкам до его корня. Будем считать, что множество элемента задается корнем дерева, в котором он лежит.

Чтобы объединить два множества - найдем корни каждого из деревьев и подвесим одно из деревьев к другому.

Асимптотика такой реализации - $O(n)$ на запрос.

Наивная реализация

vector<int> p;

void init(n) {
    p.resize(n);
    iota(p.begin(), p.end(), 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;
    }
    p[root_i] = root_j;
}

Оптимизации

Ранговая эвристика

Первая оптимизация, которую мы применим - ранговая эвристика. Будем для каждой вершины поддерживать размер ее поддерева, а при объединении - подвешивать дерево с меньшим размером к дереву с большим.

В таком случае асимптотика ответа на запрос резко уменьшится и станет равна $O(\log n)$. Действительно: пусть $size(v) = s$, тогда максимальная глубина вершины в дереве с корнем $v$ будет равна $log_2 s$, потому что каждый раз, когда глубина вершины увеличивается на 1 - размер ее дерева увеличивается хотя бы вдвое. А раз максимальная глубина - $\log_2 s$, то максимальная глубина вершины во всем дереве - $\log_2 n$, а значит, ответ на запрос будет делаться за $O(\log n)$.

Вместо размеров можно использовать ранги - максимальную глубину в поддереве вершины, эта оптимизация работает так же и дает такую же асимптотику.

Эвристика сжатия путей

Дополнительно к ранговой эвристике используем ещё одну: каждый раз, когда будем узнавать корень дерева вершины - будем подвешивать её непосредственно к корню. Это позволит дополнительно уменьшить расстояния от вершин до корня. Здесь не будет доказательства данного факта (поскольку оно слишком сложное), но оказывается, что тогда асимптотика ответа на запрос равна $O(\alpha(n))$. Здесь $\alpha(n)$ - обратная функция Аккермана, которая растёт настолько медленно, что для любых разумных $n: \alpha(n) \le 5$, то есть в среднем ответ на запрос будет получен за 5 операций.

Итоговый алгоритм (с эвристиками)

vector<int> p;
vector<int> size;

void init(n) {
  p.resize(n);
  p.iota(p.begin(), p.end(), 0);
  size.resize(n, 1);
}

int GetRoot(int i) {
  if (p[i] == i) {
    return i;
  }
  return p[i] = GetRoot(p[i]);
}


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

  if (root_i == root_j) {
    return;  
  }

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

Алгоритм Крускала

Остов в неориентированном графе - набор рёбер графа, образующий связный подграф. Минимальный остов во взвешенном неориентированном графе - остов, имеющий наименьшую возможную сумму рёбер.

Алгоритм Крускала (Краскала) решает задачу поиска минимального остова в графе. Работает очень простым образом: отсортируем все рёбра по возрастанию их весов, теперь будем их добавлять в миностов начиная с наименьшего. Очередное ребро будем добавлять, если оно соединит две компоненты связности в текущем миностове. Для проверки этого свойства используем СНМ.

Доказательство корректности

Допустим, наш алгоритм некорректен и в итоге мы получим остов, не являющийся минимальным. Рассмотрим какой-нибудь миностов и сравним с нашим.

Очевидно, что в нашем остове найдётся ребро, которого нет в миностове. Добавим это ребро в миностов. Ясно, что после этого в миностове появится цикл. Рассмотрим этот цикл. Из нашего алгоритма следует, что на этом цикле есть ребро с весом не меньше того, что мы добавили: действительно, если у всех рёбер на цикле вес меньше, чем у добавленного ребра, то мы бы добавили все эти рёбра и не добавили только что взятое. Заметим, что тогда из миностова можно выкинуть такое ребро и добавить наше, тогда миностов останется миностовом.

Таким образом можно сделать с каждым нашим ребром, которого нет в миностове, и в итоге получится, что вес миностова равен весу нашего остова. Противоречие.

Реализация

Используется реализация СНМ, приведённая выше

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;
vector<Edge> ans;

sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
    return a.weight < b.weight;
});

for (auto e : edges) {
    if (GetRoot(e.from) != GetRoot(e.to)) {
        ans.push_back(e);
        Merge(e.from, e.to);
    }
}

Асимптотика алгоритма - $O(ElogE)$