Given an undirected weighted graph $G(V,E)$, where the number of edges is $|V|+10$, how can I find the minimum spanning tree of $G$ in $O(|V|)$?
Kruskal's algorithm is out of the question, since sorting alone is $O(|V|\log |V|)$, so I thought maybe using Prim's algorithm with minimum binary heap, but still - every iteration will cost $\log |V|$ for updating vertices keys in the heap, so altogether it's $|V|\log |V|$.
I know that the key here is to use the fact that $|E|=|V|+10$, so I start thinking maybe removing the 11 edges with the biggest weights, as long as the graph stays connected, but that's obviously a bad idea since it'll - again - require sorting.
I just can't figure it out. Any help would be greatly appreciated.