Depth First Search(DFS)
Given a graph, print the number of connected components and weight of the heaviest component.
Keep a count variable and every time the dfs function gets called from main increase the value of count by 1, this way one can find the number of connected components.
Whenever the dfs function gets called from main a new component is explored, while exploring make sure that you add up the weights of nodes belonging to this component. Return the total weight, compare it with heaviest variable which stores the weight of heaviest component by far, and updates it.
The pseudo code of the modified dfs function for finding the weight of a component:
int dfs(i) // Return type is changed to an integer as this function returns the weight of a component
vis[i]←1 // ith node is marked visited (same as the standard dfs function) sum←i // sum stores the weight of all nodes encountered during the exploration from this node for each node j in adjacency list of i: // same as standard dfs function if(!vis[j]) sum ← sum + dfs(j) // apart from calling the dfs function (as in the standard dfs function) sum is also updated return sum // finally the weight of the component is returned
The above pseudo code explains how to find the weight of a component. Finding the number of connected components is explained in the quick explanation section. Refer the solution for any query.