1741. The Cheapest Plan For Every Piece
An UNDIRECTED graph has n vertices and m edges, edge i joining u and v
at cost w. Choose a set of edges that leaves every pair of vertices joined
whenever SOME route joined them to begin with, at the smallest total cost.
Print two integers: that smallest total, and the number of connected pieces the graph has.
4 vertices, 1-2 (1), 2-3 (2), 3-4 (3), 1-4 (9) -> 6 1
4 vertices, 1-2 (5), 3-4 (7) -> 12 2
1 vertex, no edges -> 0 1
2 vertices, 1-2 (4), 1-2 (4) -> 4 1
Such a set is a MINIMUM SPANNING FOREST: one cheapest tree inside each piece. When the graph is connected it is a minimum spanning TREE and the second number is 1.
## Why a forest and not just a tree
Problem 389 asks the same question and prints -1 when the graph cannot be
connected. That answer is useless to anyone who actually has a disconnected
network, and it also hides the fact that Kruskal's algorithm needs no change at
all: it just stops after picking n - c edges instead of n - 1. Printing the
piece count alongside the total says exactly how much the network is missing.
## The three things that have to be said
directed? no.
self-loops? allowed, and never chosen: the two ends are already joined.
parallel edges? allowed, and the cheaper copy is taken and the other skipped.
disconnected? allowed, and this is the point of the problem.
## Watch the size of the total
A forest holds up to n - 1 edges, each costing up to 10^9, so the total
reaches about 2 * 10^14. A signed 32-bit integer stops at 2147483647, so the
accumulator must be 64-bit. The INDIVIDUAL costs fit in 32 bits comfortably; it
is only the running sum that does not.
## What most people try first
Taking the cheapest edge at each vertex, or growing greedily from vertex 1 without a check, and ending up with a cycle. The structure needed is a way to ask "are these two already joined", and that is what a disjoint set is for.
The other common first attempt is to sort the edges and take the first n - 1.
On the first example above that takes 1-2 (1), 2-3 (2), 3-4 (3) and gets
the right answer by luck; on 1-2 (1), 1-2 (2), 2-3 (3), 3-4 (4) it takes the
first three and leaves vertex 4 out while using the duplicate edge twice.
## Kruskal
sort the edges by cost, breaking ties by input order
put every vertex in its own group
for each edge in that order:
if its two ends are in DIFFERENT groups: take it, and merge the groups
otherwise: skip it, since its ends are already joined
total = the costs of the taken edges; pieces = n - (number taken)
## Why taking the cheapest safe edge is correct
The CUT PROPERTY. Split the vertices into two sides in any way, and look at the cheapest edge crossing between them. Some cheapest forest uses it.
Proof sketch: take a cheapest forest F that joins the two sides, and suppose
it crosses with some edge f rather than the cheapest crossing edge e. Adding
e to F makes exactly one cycle, and that cycle must cross the split an even
number of times, so it contains another crossing edge, which can be removed.
The result spans the same vertices and costs no more, since e is cheapest
across. So a cheapest forest containing e exists.
Kruskal only ever takes an edge whose two ends are in different groups, and at that moment it is the cheapest edge crossing between the group of one end and everything else, because every cheaper edge has already been considered and either taken or found internal. So every edge it takes is safe, and the result is a cheapest forest.
## Cost
Time O(m log m) for the sort, plus almost constant time per disjoint-set
operation. Space O(n + m). No recursion anywhere, which matters because a
path of 200000 vertices is permitted.
## Related
Problem 389 is the connected-only version. Problem 1009 is the same question on points in the plane, where the edges are not given but computed. Problem 1010 maximises the total instead, and problem 1742 prints which edges are chosen.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000` - `u` may equal `v`, so self-loops can occur, and costs may repeat - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of edges.
Each of the next m lines contains three integers u, v and w, an undirected edge joining u and v at cost w.
Output
Print two integers on one line separated by a single space: first the smallest total cost of a set of edges that keeps every pair of vertices joined that was joined before, then the number of connected pieces the graph has. Print 0 1 when there is one vertex and no edges. Print nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.