**Problem Link:**

Contest

**Author:** Ankit

**Tester:** Shubhankar

**Editorialist:** Ankit

**DIFFICULTY:**

Easy

**PRE-REQUISITES:**

Depth First Search(DFS)

**PROBLEM:**

Given a graph, print the number of connected components and weight of the heaviest component.

**QUICK EXPLANATION:**

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.

**EXPLANATION:**

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.