MST Kruskal Algorithm
The MST Kruskal Algorithm is an algorithm in graph theory that computes the minimum spanning tree (MST) of a connected, undirected graph. The algorithm was developed by Joseph Kruskal in 1956 and is widely used in network design, clustering, and other optimization problems. The main idea behind the algorithm is to iteratively add edges to the MST in increasing order of their weights, while ensuring that no cycles are formed. The end result is a tree that connects all vertices in the graph with the minimum possible total edge weight.
To execute the Kruskal Algorithm, the edges of the input graph are first sorted in non-decreasing order according to their weights. Then, the algorithm goes through the sorted edges and, for each edge, checks if the two vertices it connects have already been connected by the MST. If not, the edge is added to the MST, and the two vertices are considered connected. This process is repeated until all vertices are connected, or equivalently, when the MST has (n-1) edges, where n is the number of vertices in the graph. To efficiently check if two vertices are connected, a disjoint-set data structure, also known as a union-find data structure, is typically used. The algorithm's time complexity is O(E log E), where E is the number of edges in the graph, making it efficient for solving large-scale problems.
/**************************************************************************************
Minimum spanning tree using Kruskal algorithm with DSU. O(MlogM)
Based on problem 1377 from informatics.mccme.ru:
http://informatics.mccme.ru/mod/statements/view3.php?id=261&chapterid=1377
**************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 20500;
struct edge {
int from, to, w;
};
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int n, m;
vector <edge> e;
int st[MAXN];
long long ans;
int getSet(int x) {
if (st[x] == x)
return x;
st[x] = getSet(st[x]);
return st[x];
}
void unite(int a, int b) {
a = getSet(a); b = getSet(b);
if (rand() & 1)
swap(a, b);
st[a] = b;
}
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
edge add;
scanf("%d %d %d", &add.from, &add.to, &add.w);
e.push_back(add);
}
for (int i = 1; i <= n; i++)
st[i] = i;
sort(e.begin(), e.end(), cmp);
for (int i = 0; i < (int) e.size(); i++) {
int from = getSet(e[i].from), to = getSet(e[i].to);
if (from != to) {
ans += e[i].w;
unite(from, to);
}
}
cout << ans << endl;
return 0;
}
