This exercise is about the linked-list representation of disjoint sets with the union-by-size heuristic and the...

 

Transcribed Image Text:

This exercise is about the linked-list representation of disjoint sets with the union-by-size heuristic and the algorithm for computing the connected components of an undirected graph. (a) During the execution of CONNECTED-COMPONENTS on a graph G = (V,E) with k connected components, where |V| = n, |E| : =m, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of n, m and k. What are these counts for the graph in the figure? a b e f h Q d g (b) Let A = {a,, an}, B = {b,..., bn}, C = {C1, Cn} Deduce a tight asymptotic bound for the time-complexity of CONNECTED-COMPONENTS on the graph G = = (V,E), where V AUBUC and E = U1 {aibi, aici, bici}. This exercise is about the linked-list representation of disjoint sets with the union-by-size heuristic and the algorithm for computing the connected components of an undirected graph. (a) During the execution of CONNECTED-COMPONENTS on a graph G = (V,E) with k connected components, where |V| = n, |E| : =m, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of n, m and k. What are these counts for the graph in the figure? a b e f h Q d g (b) Let A = {a,, an}, B = {b,..., bn}, C = {C1, Cn} Deduce a tight asymptotic bound for the time-complexity of CONNECTED-COMPONENTS on the graph G = = (V,E), where V AUBUC and E = U1 {aibi, aici, bici}.