Hi! I have the following problem regarding MSTs.
Given a complete undirected graph $$$G = (V,E)$$$ of edges only costing either 1 or 2, find a subset of the edges $$$|E'|=k$$$ for some $$$k$$$ and vertices $$$V'$$$ such that $$$(V', E')$$$ form a tree, is connected, and is of minimum cost.
The bounds for this problem is that $$$1 \le n \le 10^3$$$ and $$$1 \le k \le n - 1$$$
To me, this is very similar to an MST problem, but running a classic MST algorithm would be slow and I'm trying to do this in $$$O(|E|)$$$ time by making use of the complete graph property.