This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea is to contract the graph, i.e. collapse two or more nodes into one node. So each reduction will reduce the graph by at least half nodes. The question is to come up with implementation such that time complexity of MST-REDUCE is $O(E)$. This uses set operations. MakeSet, Union and Find-Set. I've annotated my analysis in the picture along with algorithm. I'm thinking to implement the set as linked list here. So my make-set and find-set are $O(1)$. But Union sucks: $O(V)$. Since we are doing union for all the elements, we have total $O(V^2)$ time spent in union. Which gives amortized $O(V)$. Now the problem isn't clear whether it is expecting amortized time complexity or not. So I'm wondering if any better approach is possible. Note the algorithm is running for all nodes and all edges. Hence I think amortized makes sense.
Here is my analysis (line, complexity)
1-3 $V$
4-9 $\frac{V}{2} \cdot union = \frac{V}{2} \cdot \frac{V}{2} = V^2 = V$ (amortized)
10 $V \cdot findset = V$
12-21 $E \cdot findset = E$
Since $E >= V - 1$, we have overall time complexity of $O(E)$.
0 MST-REDUCE(G, orig, c T)
1 for each v in V[G]
2 mark[v] <- FALSE
3 MAKE-SET(v)
4 for each u in V[G]
5 if mark[u] = FALSE
6 choose v in Adj[u] such that c[u,v] is minimized.
7 UNION(u,v)
8 T <- T union { orig(u,v) }
9 mark[u] <- mark[v] <- TRUE
10 V[G'] <- { FIND-SET(v) : v in V[G] }
11 E[G'] <- { }
12 for each (x,y) in E[G]
13 u <- FIND-SET(x)
14 v <- FIND-SET(y)
15 if (u,v) doesn't belong E[G']
16 E[G'] <- E[G'] union {(u,v)}
17 orig'[u,v] <- orig[x,y]
18 c'[u,v] <- c[x,y]
19 else if c[x,y] < c'[u,v]
20 orig'[u,v] <- orig[x,y]
21 c'[u,v] <- c[x,y]
22 construct adjacency list Adj for G'
23 return G', orig', c', T
