Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Kruskal: consider edges from lightest to heaviest.
  2. 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);
    }
}

Solve Minimum Spanning Tree online · All practice problems