Recall that two vertices in an undirected graph are in the same connected component if there is a path connecting them. A good algorithm to find the connected components of an undirected graph begins by calling a DFS on the first vertex. All vertices reached by the DFS are in the same connected component and are so marked. We then look through the vertex mark array until an unmarked vertex i is found. Again calling the DFS on i, all vertices reachable from i are in a second connected component. We continue working through the mark array until all vertices have been assigned to some connected component. A sketch of the algorithm is as follows:

Use the concept of potential from amortized analysis to explain why the total cost of this algorithm is Θ(jVj + jEj). 

Transcribed Image Text:

static void concom (Graph G) { int i; for (i=0; i