For a graph G=(V,E) and eligible set A, start DFS from every unvisited v in A. The vertices reached by one launch are exactly v's connected component.
Recognition signals
The prompt speaks about connected, reachable, component, group, or region.
It asks whether a state is reachable or how many groups exist, not for the fewest steps.
Successors can be generated locally and each state needs one expansion.
Exploring one branch deeply cannot invalidate the result; traversal order is immaterial.
False friends
Signal
Why it is different
Unweighted shortest path
The first DFS arrival need not use the fewest edges; use bfs-unweighted-shortest.
Dependency ordering
Directed prerequisites require indegrees or recursion colors, not plain component traversal.
Core invariant
Once marked visited, a vertex belongs to the component represented by the current search and can never join a later component.
State, transition, and processing order
Item
Definition
State
Current vertex u, global visited set, and an optional component accumulator such as size, sum, or boundary flags.
Transition
For every neighbor v of u, if v is eligible and unseen, mark it before recursing or pushing it.
Frontier / order
The call stack or an explicit LIFO stack of discovered vertices whose adjacency is not fully expanded.
Python skeleton
def components(graph):
seen, groups = set(), []
for start in graph:
if start in seen:
continue
seen.add(start)
stack, group = [start], []
while stack:
u = stack.pop()
group.append(u)
for v in graph[u]:
if v not in seen:
seen.add(v)
stack.append(v)
groups.append(group)
return groups
Correctness sketch
Soundness: every pushed vertex is connected to start through actual graph edges.
Completeness: choose a path to any reachable vertex; inductively, expanding each predecessor discovers the next vertex.
Partition: marking on discovery permits at most one push per vertex, while the outer loop launches exactly for vertices not assigned earlier.
Complexity
Time
Space
Parameters
O(V+E)
O(V)
V is the number of vertices and E the number of stored adjacency entries.
Edge cases
An empty graph yields no groups.
Every isolated vertex forms a singleton component.
A self-loop must not cause another push.
A chain of depth V can overflow Python recursion; use an explicit stack.
Error patterns
Pattern
Why it fails / fix
Marking only after pop
Several parents can push the same vertex; mark it when discovered.
Searching from one source only
That finds one component, not a partition of the entire graph.
Wrong edge direction
Omitting reverse edges for an undirected graph silently turns connectivity into one-way reachability.
Selection and exclusion rules
For grouping without a distance objective, DFS and BFS are interchangeable.
Prefer DFS when a postorder return naturally carries a region summary.
Prefer an explicit stack when depth may approach V.