We first note one structural property that allows us to use a greedy approach to solve this task. Given a graph ~G = (V, E)~, where ~V~ is the set of villages, and ~E~ is the set of roads, we color each edge ~e~ blue if it is a cobblestone road and red otherwise. This task wants to find a spanning tree of ~G~ that contains exactly ~k~ blue edges.

Consider any spanning tree ~T~. Note that if we consider a subgraph of ~T~ that contains only blue edges, we get a forest. It is known that for any two forests ~F_1~ and ~F_2~, such that ~F_1~ has ~k_1~ edges, ~F_2~ has ~k_2~ edges, and ~k_2 > k_1~, there exists some edge ~e \in F_2~ such that ~F_1 \cup \{e\}~ remains a forest. (See, e.g., Cormen et al., Chapter 16 on matroids.) This implies that to find a spanning tree with ~k~ blue edges, we can never make a mistake by taking in wrong blue edges.

With that fact, there are many ways to find a required spanning tree. We present here one solution.

The algorithm has two rounds. First, we try to find a set of "required" blue edges, i.e., these edges must be in the tree to ensure connectivity. We start by finding all connected components of a subgraph containing only red edges. We then greedily add blue edges joining different components so that the graph is connected. These blue edges added in this round form the starting blue edge set ~B~. Clearly, if we need more than ~k~ edges to connect the graph, we can be sure that there is no spanning tree with the required property.

In the second round, we start with a forest ~F~ with only edges in ~B~. We then greedily add blue edges to ~F~ while maintaining that the resulting graph ~F~ remains a forest. We keep adding until we get ~k~ blue edges in ~F~. After that, we complete the algorithm by using red edges to join different connected components in ~F~.

If we fail in any step, it means that no solution exists.

The main data structure that we use in both rounds is the union-find data structure for maintaining disjoint sets.

In the first round, to find connected components of red edges, we just union every pair of components containing end points of red edges. Before adding blue edges ~e~, we call two find subroutines to check if ~e~ joins two different components. If that's the case, we union both components. In the second round, we may proceed like the second step of the first round.

To analyze the running time, for each round, we call at most ~n~ unions and ~\mathcal O(m)~ finds. Using a set of trees with union-by-rank heuristics ensures that each operation (union or find) runs in time ~\mathcal O(\log n)~. Thus, the algorithm runs in time ~\mathcal O((n+m) \log n)~.