Let G = (V, E) be an edge-weighted undirected multigraph, that is, an undirected graph with weighted edges that may have selfloops and parallel edges. We call an edge e of G futile if either e is a...

Let G = (V, E) be an edge-weighted undirected multigraph, that is, an undirected graph with weighted edges that may have selfloops and parallel edges. We call an edge e of G futile if either e is a selfloop or if e is not the lightest edge between its two endpoints (equivalently, it is not the lightest edges among parallel edges). Since all futile edges can be considered as red edges in the MST Meta-Algorithm (every futile edge is the heaviest edge in a cycle of length 1 or 2), we can remove all futile edges from G without changing its minimum spanning tree. The operation of simplifying G removes all futile edges. Show that any edge-weighted multigraph with |V | vertices and |E| edges can be simplified in O(|V | + |E|) time. Describe an algorithm for doing so and present data structures used.