Best way to test for total reachability

Question

I have a set of nodes, each of which is connected to at least one other node. I would like to know if the connections are such that each node is reachable from every other. For example:

1--2
   |
3--4

Versus:

1--2

3--4

I am convinced this kind of reachability testing can be projected in terms of an exact cover problem, however I can't seem to get my brain wrapped around how to do so. Does anyone have any pointers, documentation, web sites, etc., on how to do this? Examples would be extremely valuable.

Update: My ignorance has betrayed me, as it would seem there are far more efficient algorithms for this kind of test. If you have one, please point me to it.

Answer 1

• start from any node and do a depth/breadth first traversal
• count number of visited node (of course, dont visit any node twice!)
• compare counted number with total number

Answer 2

There is also a fast (but quite complicated) algorithm for maintaining connectivity dynamically (i.e. under edge insertions/deletions), shown in this paper: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

The basic idea is maintaining a spanning tree. The easy cases are inserting an edge, and deleting a non spanning tree edge. The problem is when deleting a spanning tree edge, because now there is not guaranteed connectivity - we have to search efficiently an alternate route to connect the broken parts, otherwise the graph is disconnected.