Постановку задачи и описание алгоритма Крускала см. здесь.
Здесь будет рассмотрена реализация с использованием структуры данных "система непересекающихся множеств" (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);
}
}
|