Algorithms and Data Structures

3. (10 pts) Define a connected component of an undirected graph to be a subgraph where every pair of vertices are reachable from cach other by traversing through one or more edges within the same subgraph. Show that we can use a depth-first search of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex an integer label cc between I and k, where k is the number of connected components of G, such that ccfuJ-ccfv] if and only if u and v are in the same connected component. Analyze the running time of your algorithm