Question

Analyze the worst-case complexity of the algorithm below when using an optimized adjacency list to store G.

ComponentCount:

Input: G = (V, E): an undirected graph with n vertices and m edges

Input: n, m: the order and size of G, respectively

Output: the number of connected components in G

Pseudocode:

comp = n

uf = UnionFind(n)

For v in V:

For u in N(v):

If (uf.Find(v) != uf.Find(u))

uf.Union(u, v)

comp = comp - 1

End if

End for

End for

Return comp

Answer 1

plz like it

Soution Pseudocode compon uf - Union find (n) for v in vi for u in N(O): # here NGOs means neighbour of v . if ( uf. Find (u) 1 = uf. Find (v)) uf. Union (U,G) comp - comp-1 End if Time complexity worst case End for T(n) : 0 (02) End for Return comp ocluye 07 let Graph 1 (3 4 5 2 Pitially comp 6 Us 0 then N(0) = {1,2} 1 comp = 6-2 - 4 Union (01) 4 (0,2) 2 then U = 3 N(V): {4} Union (3,4) 4 comp: 4-13 (3) (012)(34) (5) v=5 then NCU) - {0} So comp = 3 (final value) So were 3 connected component for complete Grapb comp- 4-3 = 1 2 3 3 n(n-1) - 92) Time complexity Tn): (n-1) + (n-1)+(n-1) --.(n-1) ( for loop execution) n times CS Scanned with CamScanner