Practice › Graphs
Minimum Spanning Tree
Medium · Graphs · Asked at Amazon, Google, Microsoft, Samsung
The undirected weighted graph is connected. Print the total weight of a minimum spanning tree — a set of n − 1 edges connecting all nodes with the smallest possible total weight.
Input
First line: n m. Next m lines: u v w — an edge of weight w.
Output
The weight of the MST.
Constraints
- 1 ≤ n ≤ 10^5
- n − 1 ≤ m ≤ 2 · 10^5
- 1 ≤ w ≤ 10^6
Kruskal: sort edges by weight and add an edge if it joins two different components (union–find). Prim's algorithm with a heap also works.
Example 1
Input
4 5 1 2 1 2 3 2 3 4 1 1 4 4 1 3 3
Output
4
Example 2
Input
1 0
Output
0
Hints
- Kruskal: consider edges from lightest to heaviest.
- Take an edge only if its endpoints are in different components — check and merge components with union–find.
Approach
Sort the edges by weight. Union–find tracks which nodes are already connected. For each edge (u, v, w): if find(u) ≠ find(v), add w to the total and union the sets; otherwise the edge would close a cycle, so skip it. The cut property guarantees the chosen edges form a minimum spanning tree. Use 64-bit totals.
Complexity: O(m log m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
int n, m;
cin >> n >> m;
vector<array<long long, 3>> edges(m);
for (auto &e : edges) cin >> e[1] >> e[2] >> e[0]; // stored as (w, u, v)
sort(edges.begin(), edges.end());
par.resize(n + 1);
iota(par.begin(), par.end(), 0);
long long total = 0;
for (auto &e : edges) {
int a = find(e[1]), b = find(e[2]);
if (a != b) par[a] = b, total += e[0];
}
cout << total << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
edges = sorted((data[4 + 3 * i], data[2 + 3 * i], data[3 + 3 * i]) for i in range(m))
par = list(range(n + 1))
def find(x):
while par[x] != x:
par[x] = par[par[x]]
x = par[x]
return x
total = 0
for w, u, v in edges:
a, b = find(u), find(v)
if a != b:
par[a] = b
total += w
print(total)Java solution
import java.util.*;
import java.io.*;
public class Main {
static int[] par;
static int find(int x) {
while (par[x] != x) {
par[x] = par[par[x]];
x = par[x];
}
return x;
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
long[][] edges = new long[m][3];
for (int i = 0; i < m; i++) {
in.nextToken();
edges[i][1] = (long) in.nval;
in.nextToken();
edges[i][2] = (long) in.nval;
in.nextToken();
edges[i][0] = (long) in.nval;
}
Arrays.sort(edges, (a, b) -> Long.compare(a[0], b[0]));
par = new int[n + 1];
for (int i = 0; i <= n; i++) par[i] = i;
long total = 0;
for (long[] e : edges) {
int a = find((int) e[1]), b = find((int) e[2]);
if (a != b) {
par[a] = b;
total += e[0];
}
}
System.out.println(total);
}
}