Rare Routing

Given an undirected graph and a starting node, return how many nodes are reachable from the start, including the start itself.

rareRouting(graph, start)

Input format: edges | start, edges as a,b pairs.

Examples

edges a,b b,c d,e, start a   // → 3   (a, b, c)
edges a,b b,c d,e, start d   // → 2   (d, e)
edges (none), start a        // → 1

Walkthrough

Thinking it through

"How many nodes can I reach from here" asks for the size of the start's connected component — every node joined to it by some chain of edges. No weighting or shortest-path concern, just reachability, so BFS or DFS work equally well.

Why you need to track visited nodes

The graph can contain cycles, so a naive traversal revisiting nodes could loop forever or waste work. Maintain a visited set: arriving at a node, check it first. Already visited means stop; otherwise mark it visited and continue to its neighbors.

Building the approach

Start with an empty visited set, explore from the start node.
If the current node is already visited, stop this branch.
Otherwise add it to visited, then explore all its neighbors the same way.
Once exploration is exhausted, the visited set's size is the answer.

DFS falls out of recursion naturally: visit, mark, recurse into each neighbor. BFS uses a queue instead, processing in waves. Both visit the same set of nodes — the order differs, the count doesn't.

Handling the edge cases

An isolated start still counts as 1 — it reaches itself trivially, which is why marking the start visited happens before looking at any neighbors. Nodes in other components are never visited and correctly excluded, since reachability respects component boundaries.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.