Connected Components

A connected component of an undirected graph is a maximal island of vertices you can walk between — two vertices share a component exactly when a path joins them. Counting them takes an outer sweep that starts a fresh flood-fill at each vertex no earlier fill has colored — O(V + E) time, and the number of fills started is the component count.

The catch that trips people up: a single DFS or BFS finds only one island — the one it started in — because a traversal only reaches what is connected to where it began. The outer sweep exists to catch every island the first fill never touched.

That outer loop can look wasteful: most of the time it lands on a vertex an earlier fill already claimed and does nothing but move on. Those skips are the whole point. Each one is proof that the vertex was already accounted for, and the handful of vertices that are not skipped — the ones still uncolored when the sweep reaches them — are exactly the seeds of the components. Drop the outer loop and keep a single fill from vertex 0, and you would report one component and silently miss every other island.

Why the Outer Sweep Exists

The algorithm is two nested loops, and the outer one is the star. The outer loop is a plain for start in range(n) over every vertex id. When it reaches a vertex that already carries a color, it does nothing and moves on. When it reaches an uncolored vertex, it has found new ground: it opens a new component and flood-fills the entire island reachable from that vertex before the sweep continues.

The flood-fill itself is ordinary graph traversal — this lesson uses an iterative DFS with an explicit stack, marking each vertex the moment it is pushed. Push the seed, then repeatedly pop a vertex and push its still-uncolored neighbors, until the stack drains. Every vertex it reaches gets stamped with the current component's color. Because the graph is undirected, "reachable" is symmetric: if the fill can get from a to b, it can get back, so a fill started anywhere in an island colors the whole island. (For a directed graph the analogous idea — strongly connected components — needs a different algorithm, such as Kosaraju’s two-pass method or Tarjan’s one-pass method; plain reachability is not symmetric when edges have direction.)

Swap the stack for a queue and the fill becomes BFS instead of DFS — the vertices get colored in a different order within each island, but the components come out identical. That is the deeper point: the partition into components is a property of the graph, not of how you explore it. The outer sweep is what does the real work; the fill is an interchangeable detail.

Reach for this when you need to label or count the disconnected groups of a static undirected graph — clusters in a network, islands in a grid, related items. If edges keep arriving and you want the grouping maintained online, Union-Find tracks the same components incrementally without re-sweeping. And if your edges are directed, plain reachability is no longer symmetric, so you need strongly connected components instead of this.

Connected Components Step by Step

The default graph has 8 vertices in three visibly separate islands: a triangle {0, 1, 2} (edges 0-1, 1-2, 2-0), a pair {3, 4} (edge 3-4), and a chain {5, 6, 7} (edges 5-6, 6-7). The ids run left to right across the islands, so the outer sweep reads as a scan from 0 to 7. Watch the counter climb only three times.

1. Sweep reaches 0 — uncolored. Open component #1 and flood-fill from 0. Push 0; pop it and its neighbors 1 and 2 are both uncolored, so color them into #1 and push them. Pop 2 (its neighbors 0 and 1 are already in #1 — nothing new), pop 1 (same), and the stack is empty. Component #1 sealed: {0, 1, 2}.
2. Sweep reaches 1 — already in #1. Skip.
3. Sweep reaches 2 — already in #1. Skip. (Two skips in a row: the triangle's other two vertices were colored by the fill before the sweep ever got to them.)
4. Sweep reaches 3 — uncolored. Open component #2. Push 3; pop it, color its neighbor 4 and push it; pop 4 (neighbor 3 already in #2); stack empty. Component #2 sealed: {3, 4}.
5. Sweep reaches 4 — already in #2. Skip.
6. Sweep reaches 5 — uncolored. Open component #3. Push 5; pop it, color 6 and push; pop 6, color 7 and push; pop 7 (neighbor 6 already in #3); stack empty. Component #3 sealed: {5, 6, 7}.
7. Sweep reaches 6 — already in #3. Skip.
8. Sweep reaches 7 — already in #3. Skip. The sweep runs off the end.

Final tally: 3 components — {0, 1, 2}, {3, 4}, {5, 6, 7}. The outer loop iterated 8 times, started a fill 3 times, and skipped 5 times. Three fills, three components: that equality is the takeaway. Every one of the 8 vertices was either the seed of a new component or an already-colored skip — never both, never neither, which is exactly why every vertex ends up in exactly one component.

The presets bracket the idea, and the default deliberately leaves out the case people forget — so try them. One graph wires all vertices into a single connected blob: the sweep opens one fill, then every remaining iteration is a skip — the outer loop is almost entirely skips, and the answer is 1. Scattered is the one to reach for next: a vertex with no edges at all is still its own component, and you can watch the sweep open a fill on it — the boundary that a wrong count almost always misses. All isolated takes that to the limit — no edges anywhere, so every vertex is its own component and the sweep starts n fills with zero skips. Flip between them and the counter tracks the number of fills every time.

Time and Space Complexity

The outer loop touches each of the V vertices once. Across all the fills combined, every vertex is pushed and popped once and every edge is examined from each endpoint — O(V + E) total, no matter how the vertices split into components (one giant fill or V tiny ones costs the same). Space is O(V): the visited/color record plus the fill's stack, which can hold O(V) pending vertices in the worst case (for example, after expanding the center of a star).

Edge Cases

• A single vertex — one component. The sweep opens a fill, the fill finds no neighbors, done.
• An isolated vertex (no edges) — still its own component. This is the case people forget: connectivity does not require edges, only that nothing else is reachable. The outer loop must still land on it and open a fill.
• A fully connected graph — one component; the sweep does one fill and then skips every other vertex.
• All vertices isolated — n components, the maximum. The sweep is all fills and no skips.

Common Mistakes

1. Running one traversal and calling it done. A single DFS/BFS from a start vertex finds one component — the start's. Without the outer loop restarting at each uncolored vertex, every other island is invisible.
2. Forgetting isolated vertices. A vertex with no edges is a component of size one. Skip it and your count is short and your partition is wrong.
3. Marking visited on pop instead of on push. Mark a vertex the instant you push it, or it can be pushed several times before it is ever popped — inflating the stack and, in some formulations, corrupting the count.
4. Confusing connected components with strongly connected components. Connectivity is symmetric only for undirected graphs. On a directed graph, reachable-from-a and reachable-from-b are different questions, and you need an SCC algorithm, such as Kosaraju’s or Tarjan’s, not this one.
5. Believing the fill method matters. DFS or BFS, stack or queue — the components are the same. What determines the answer is the graph's structure and the outer sweep, not the order you happen to color each island.