I need to get the MST of a complete graph where all edges are defaulted to weight 3, and I'm also given edges that have weight 1.

Here is an example

5 4 (N, M)
1 5
1 4
4 2
4 3

Resulting MST = 3 -> 5 -> 1 -> 4 -> 2

Where the first row has the number of total nodes (N), the amount of 1-weight edges (M) and all of the following (M) rows contain an edge that has weight of 1.

I tried constructing a complete graph and updating weights of given edges to 1, but the spacial complexity is too big for a problem that contains up to 10^5 1-weight edges.

CodePudding user response：

Use Kruskal's algorithm to construct the minimum spanning forest of the graph of only the 1-weight edges. The total weight of the minimum spanning tree of the entire graph will then be the number of edges in the minimum spanning forest (times 1) plus the cost of the edges to connect the trees in the forest (number of trees minus 1 times the weight of 3) plus the cost of one 3-weight edge each to connect the remaining nodes not in the original minimum spanning forest.