Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств

Постановку задачи и описание алгоритма Крускала см. здесь.

Здесь будет рассмотрена реализация с использованием структуры данных "система непересекающихся множеств" (DSU), которая позволит достигнуть асимптотики O (M log N).

Описание

Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. своё множество) с помощью вызова функции DSU MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра (в порядке сортировки) и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union - также за O (1). Итого мы получаем асимптотику O (M log N + N + M) = O (M log N).

Реализация

Для уменьшения объёма кода реализуем все операции не в виде отдельных функций, а прямо в коде алгоритма Крускала.

Здесь будет использоваться рандомизированная версия DSU.

vector<int> p (n);

int dsu_get (int v) {
 return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));
}

void dsu_unite (int a, int b) {
 a = dsu_get (a);
 b = dsu_get (b);
 if (rand() & 1)
 swap (a, b);
 if (a != b)
 p[a] = b;
}

... в функции main(): ...

int m;
vector < pair < int, pair<int,int> > > g; // вес - вершина 1 - вершина 2
... чтение графа ...

int cost = 0;
vector < pair<int,int> > res;

sort (g.begin(), g.end());
p.resize (n);
for (int i=0; i<n; ++i)
 p[i] = i;
for (int i=0; i<m; ++i) {
 int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
 if (dsu_get(a) != dsu_get(b)) {
 cost += l;
 res.push_back (g[i].second);
 dsu_unite (a, b);
 }
}