Given: graph G. Say G has k (connected) components 1 k. Clearly, k n.

We would like to record which vertex is in which component: array comp[1] comp[n] is used for this purpose; value of comp[i] = j means, vertex i is in component j.

Given graph G and array comp[1] comp[n], design an algorithm by appropriately modifying dfs(depth first search) that sets comp[x] to i provided vertex x is in component number i.

Must run in O(m + n) time!!! Present a complete algorithm.