How do I find out if a graph is really in two separate pieces?

A graph is in two separate pieces exactly when one walk from one point cannot reach every point. Walk from any point until nothing new is reachable, mark every point it reached, then start a fresh walk at any still unmarked point; each walk discovers one piece, so the number of walks is the number of pieces.

Take six points $a,b,c,d,e,f$. In the first three, link $a$ to $b$, $b$ to $c$, and $c$ to $a$. In the second three, link $d$ to $e$ and $e$ to $f$. There is no link between any of $a,b,c$ and any of $d,e,f$. Start at $a$ with the pile holding just $a$. Pop $a$, mark it seen, and push its neighbours $b$ and $c$, so the pile is $[b,c]$. Pop $c$, mark it seen, and push its unseen neighbour $b$, so the pile becomes $[b,b]$. Pop $b$, mark it seen, find no unseen neighbours, leaving pile $[b]$. Pop the remaining $b$, see that it is already seen, and skip it. The pile is empty. This walk reached $a,c,b$, three points. The point $d$ was never seen, so start a second walk at $d$. Pop $d$, mark it, push $e$. Pop $e$, mark it, push $f$. Pop $f$, mark it, and stop with the pile empty. This walk reached $d,e,f$, another three points. No unvisited point remains. There were two starts, so there are two pieces.

The arithmetic of the count is the whole test. The first walk processed three points, the second processed three points, and $3+3=6$ is every point in the graph. No point was processed twice. The five links were looked at when their endpoints were processed, so the total work is one pass over six points and five links, not one full search for each piece. If the first walk had reached all six points, the fresh-start loop would have found no unvisited point afterwards and the number of starts would be one. That is what it means for the graph to be in one piece.

The natural guess is that separate pieces are obvious: a lonely point, a gap in a drawing, or a cluster that looks detached. That is not a test. Two large, busy clusters can each have many links inside them and share no link at all. In the example there are six points and five links, and the graph is in two pieces; a connected graph on six points can also have five links, namely a tree. So neither the number of links nor the busyness of a region tells you the number of pieces. A split is a reachability fact. The only reliable method is to exhaust one walk until it stops, then look for a point it never marked, and start again there.