An IT team is connecting n offices 0 .. n-1. The candidate links are links[i] = [u, v, cost]
(undirected, parallel links possible). For contractual reasons some links must be built:
required is a list of indices into links. Build every required link plus any other links you like
so that all offices are connected, minimising the total cost (required links are always paid for,
even if they form a loop).
Return the minimum total cost, or -1 if the offices cannot all be connected.
Examples
Input: n = 4, links = [[0,1,1],[1,2,1],[2,3,1],[0,3,9]], required = [3]
Output: 11
Explanation: 0-3 (9) is forced; then 0-1 (1) and 1-2 (1) finish the job.
Input: n = 3, links = [[0,1,2],[0,1,3],[1,2,1]], required = [0, 1]
Output: 6
Explanation: both parallel links are forced (2 + 3); link 1-2 adds 1.
Constraints
1 <= n <= 10**4,0 <= len(links) <= 2 * 10**4,0 <= cost <= 10**6requiredholds distinct valid indices.- Target
O(E log E)time.
Goals
- Pre-merge the components joined by required edges
- Complete the tree greedily with the remaining edges
- Detect a plan that still leaves offices disconnected