Skills101
← All coding problems

Minimum Spanning Tree (Kruskal)

mediumGraphs II+20 XPTime limit 2s

A state wants to connect n villages with fibre cable. Laying cable on a possible route u v w costs w lakh rupees. Choose routes so that every village is connected (directly or through others) at the minimum total cost.

Input:

  • line 1: n m
  • next m lines: a possible route u v w (two-way)

Output: the minimum total cost, or -1 if it is impossible to connect all villages.

Constraints: 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 3·10⁴, 1 ≤ w ≤ 10⁵, u ≠ v; several routes may join the same pair. The answer fits in a 32-bit signed integer.

Think about it: Kruskal's algorithm: sort routes by cost and take each one that joins two different components (check with Union-Find); skip routes that would make a cycle. You need exactly n − 1 routes. O(m log m). Prim's algorithm with a min-heap works too.

Sample input 1

4 5
1 2 1
2 3 4
1 3 3
3 4 2
2 4 5

Sample output 1

6

Sample input 2

3 1
1 2 7

Sample output 2

-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.