389. Cheapest Way to Join Everything
Same input as problem 388, different question. Choose a set of edges that
leaves every vertex connected to every other, at the smallest total weight, and
print that total. Print -1 if the graph cannot be connected at all.
That set is a minimum spanning tree, and this is the pairing worth studying: the same graph, one question about reaching ONE vertex cheaply and one about reaching ALL of them cheaply, with different answers. On the second sample problem 388 answers 8 and this answers 9.
The method is Kruskal's algorithm, and it is the union-find of problem 387 with the edges sorted. Take edges cheapest first; keep one when its ends are in different groups, since it joins something new; skip it when they are already connected, since it would be redundant exactly as in 387.
Any spanning tree has n - 1 edges. If you finish with fewer, the graph was
disconnected, and that is the -1 case.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ w ≤ 1000000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains three integers u, v and w: an
undirected edge between those vertices whose weight is w. Vertices are
numbered 1 to n.
Output
Print one integer, the smallest total weight that connects every vertex, or
-1 if that is impossible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.