Loading...
Loading...
Loading...
A college wants internet in all n buildings on its campus, numbered 1 to n. A contractor offers m possible cables. Each cable joins two buildings in both directions and has a cost in rupees.
The college picks some of the offered cables so that every building can reach every other building, maybe through other buildings. Print the smallest possible total cost. If even all the cables together cannot connect every building, print -1. With a single building, the cost is 0.
int limit, so use longExample 1
Input
4 5 1 2 3 2 3 1 3 4 4 4 1 2 1 3 5
Output
6
Pick 2-3 (1), 4-1 (2) and 1-2 (3). Every building is connected for 6 rupees.
Example 2
Input
4 2 1 2 5 3 4 6
Output
-1
No cable joins the pair 1, 2 with the pair 3, 4.
Try the problem first. Open one hint at a time.
The chosen cables never need a loop: if they formed one, you could drop the costliest cable on it and stay connected.
Try cables from cheapest to most costly. Take a cable only if it joins two buildings that are not yet connected.
Keep groups of connected buildings with a parent array and a find method. A cable inside one group is skipped.
Add costs in a long. If fewer than n − 1 cables were taken at the end, the buildings cannot all be connected.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor