Amazon Online Assessment (OA) - Min Cost to Repair Edges (Minimum Spanning Tree II)

There's an undirected connected graph with n nodes labeled 1..n. But some of the edges has been broken disconnecting the graph.

Find the minimum cost to repair the edges so that all the nodes are once again accessible from each other.

Input

n, an int representing the total number of nodes.

edges, a list of integer pair representing the nodes connected by an edge.

edgesToRepair, a list where each element is a triplet representing the pair of nodes between

which an edge is currently broken and the cost of repairing that edge, respectively (e.g. [1, 2, 12] means to repair an edge between nodes 1 and 2, the cost would be 12).

Examples

Example 1:

Input: n = 5, edges = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]], edgesToRepair = [[1, 2, 12], [3, 4, 30], [1, 5, 8]]
Output: 20
Explanation:

There are 3 connected components due to broken edges: [1], [2, 3], and [4, 5].

We can connect these components into a single component by repairing the edges between nodes 1 and 2, and nodes 1 and 5 at a minimum cost 12 + 8 = 20.

Example 2:

Input:

n = 6, edges = [[1, 2], [2, 3], [4, 5], [3, 5], [1, 6], [2, 4]], edgesToRepair = [[1, 6, 410], [2, 4, 800]]

Output: 410

Example 3:

Input:

n = 6, edges = [[1, 2], [2, 3], [4, 5], [5, 6], [1, 5], [2, 4], [3, 4]], edgesToRepair = [[1, 5, 110], [2, 4, 84], [3, 4, 79]]

Output: 79

Try it yourself


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ