So as far as what does this algorithm accomplish, well,

it certainly finds every connected component.

There is absolutely no way it can miss a node because this for

loop literally walks through the nodes, all of them, one at a time.

So you're not going to miss a node.

Moreover, we know that as soon as you hit a connected component for

the first time, and you do breadth-first search from that node,

you're going to find the whole thing.

That the breadth-first a search guarantee.

As far as what's the running time, well it's going to be exactly what we want.

It's going to be linear time, which again means proportional to the number of edges

plus the number of vertices.

And again depending on the graph, one of these might be bigger that the other.

So why is it O of m plus n?

Well as far as the nodes, we have to do this initialization there where we mark

them all as unexplored, so that takes constant time per node.

We have just the basic overhead of a for loop, so that's constant time per node.

And then we have this check, constant time per node, so that's O of n.

And then recall we proved that within breath for research,

you do a amount of work proportional.

You do constant time for each node in that connected component.

Now, each of the nodes of the graph is in exactly one of the connected components.

So you'll do constant time for

each node in the BFS in which you discover that node.

So that's again, o of n over all of the connected components.

And as far as the edges, note we don't even bother to look at edges until

we're inside one of these breadth first search calls.

They played no role in the outer for loop or in the pre-processing.

And remember what we proved about an indication of breadth first search.

The running time, you only do constant amount of work

per edge in the connected component that you're exploring.

In the worst case, you look at an edge once from either endpoint and

each of that triggers a constant amount of work.

So when you discover a given connected component,

the edge work is proportional to the number of edges in that kind of component.

Each edge of the graph is only in exactly one of the connect components, so

over this entire for loop, over all of these BFS calls.

For each edge of the graph, you'll only be responsible for

a constant amount of work of the algorithm.

So summarizing because breadth-first search from a given starting node.

That is, works in time proportional to the size of that component, piggybacking on

that sub routine and looping over all of the nodes of the graph.

We find all of the connecting components in time proportional to the amount of

edges and nodes in the entire graph.