Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / c

Run Kruskal's algorithm in nonincreasing order of edge weight, accepting an edge exactly when its endpoints belong to different current connected components. Use a disjoint-set data structure to test and merge those components. Stop after accepting $|V|-1$ edges.

Equivalently, apply ordinary Kruskal's algorithm to $w^{\prime }(e)=-w(e)$. For every spanning tree,so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a maximum spanning tree. Equal weights may be processed in any fixed order. Sorting dominates the time complexity, giving $O(|E|\log |E|+|V|)$ with the usual efficient disjoint-set data structure.