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

Pseudocode:

comp = n

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

For v in V: // O(V)

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

        If (uf.Find(v) != uf.Find(u)) // O(log n)

            uf.Union(u, v)

            comp = comp - 1

        End if

    End for

End for

Return comp

Total time complexity = O(V *V* logV)

i.e