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

Answer:-

comp = n

uf = UnionFind(n) // O(log V)

For v in V: // O(V)

    For u in N(v): // O(V) in worst case

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

            uf.Union(u, v)

            comp = comp - 1

        End if

    End for

End for

Return comp

The total time complexity in worst case is = O(V*V*logV)

i.e O(V^2logV)

Please UPVOTE thank you...!!!