A connected undirected graph has n vertices, numbered 0 to n - 1, and m weighted edges. Print the total weight of a minimum spanning tree: the cheapest set of edges that connects every vertex. No two edges join the same pair of vertices.
What to build
A program that finds the total weight of a minimum spanning tree.
Requirements
- Use Prim's or Kruskal's algorithm.
- Connect every vertex using exactly
n - 1edges. - Print the total weight.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has an edge u v weight (1 ≤ weight ≤ 1000). The graph is connected.
Output
The total weight of a minimum spanning tree.
Constraints
1 ≤ n ≤ 100, 0 ≤ m ≤ 1000 and 1 ≤ weight ≤ 1000. The graph is connected.
Example
Input:
5 7
0 1 4
0 2 1
1 2 2
1 3 5
2 3 8
3 4 2
2 4 10
Output:
10
Why it works
The cheapest edge crossing between any two groups of vertices is always safe to use, and both algorithms only ever take such an edge.
Examples
5 7 0 1 4 0 2 1 1 2 2 1 3 5 2 3 8 3 4 2 2 4 10
10
2 1 0 1 5
5
Hints
Hint 1
Prim's algorithm with a matrix is enough for 100 vertices: key[v] = the cheapest edge joining v to the tree so far.
Hint 2
Each round, add the vertex not in the tree with the smallest key, add its key to the total, and update the keys of its neighbours.
Hint 3
Kruskal's algorithm with union-find also works.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#define INF 1000000000
int w[100][100];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
w[u][v] = w[v][u] = c;
}
int key[100], in_tree[100];
for (int i = 0; i < n; i++) {
key[i] = INF;
in_tree[i] = 0;
}
key[0] = 0;
int total = 0;
for (int round = 0; round < n; round++) {
int u = -1;
for (int i = 0; i < n; i++)
if (!in_tree[i] && (u == -1 || key[i] < key[u])) u = i;
in_tree[u] = 1;
total += key[u];
for (int v = 0; v < n; v++)
if (w[u][v] && !in_tree[v] && w[u][v] < key[v]) key[v] = w[u][v];
}
printf("%d\n", total);
return 0;
}