#228MediumGraphs· Minimum Spanning Tree with Kruskal

Cheapest Fiber Backbone

A telecom provider wants to connect `n` regional sites (numbered `0` to `n - 1`) with fibre. Surveyors listed the possible cable routes as `[a, b, cost]`: a cable between sites `a` and `b` costs `cost` and works in both directions. Choose a set of routes so that every site can reach every other site through the laid cables, minimising the total cost. Return that minimum total cost, or `-1` if the listed routes cannot connect all sites. A single site needs no cable, so the cost is 0.

Input format

`n`: number of sites; `links`: array of `[a, b, cost]`.

Output format

An integer: the minimum total cost, or -1 if the sites cannot be connected.

Examples

Input: n = 4, links = [[0, 1, 3], [1, 2, 4], [0, 2, 1], [2, 3, 2], [0, 3, 9]]

Output: 6

Take the cables costing 1, 2 and 3 (0-2, 2-3, 0-1): all four sites are connected for 6. The 4-cost and 9-cost cables are never needed.

Input: n = 3, links = [[0, 1, 5]]

Output: -1

Site 2 has no cable option, so the network cannot be connected.

Input: n = 1, links = []

Output: 0

One site is trivially connected at no cost.

Constraints

1 <= n <= 10^5
0 <= links.length <= 2 * 10^5
0 <= a, b < n, a != b
0 <= cost <= 10^4
Parallel routes between the same two sites are allowed.

#minimum-spanning-tree
#kruskal
#union-find
#graph
#greedy