Identifying the connected component pattern

Many graph problems require finding and processing some or all the connected components of a graph. These are generally medium or hard problems where we are given an undirected graph and need to find the aggregated value of some function f over all the nodes in all the connected components. Some problems may even go further and require aggregating all the component-level aggregates over another function g. Either depth-first or breadth-first traversal can traverse all connected components to solve such problems efficiently.

If the problem statement or its solution follows the generic template below, it can be solved by traversing all the connected components.