Shortest Hop Count

Problem Statement

You're given an undirected graph — a set of numbered nodes connected by edges, where each edge can be crossed in either direction — along with a starting node, the source. For every node in the graph, find the minimum number of edges you'd need to cross to reach it from the source. If a node can't be reached from the source at all, its answer is -1; the source's own distance to itself is always 0.

Input Format

The input has m + 2 lines:

• Line 1: two integers, n and m — the number of nodes (numbered 0 to n - 1) and the number of edges.
• The next m lines: each contains two integers, u and v, meaning there's an undirected edge between node u and node v.
• The final line: a single integer, the source node.

Output Format

Print one line containing n space-separated integers: dist[0], dist[1], ..., dist[n-1], where dist[i] is the minimum number of edges on a path from the source to node i, or -1 if node i is unreachable from the source.

Example Walkthrough

Take the second sample: 3 nodes, edges 0-1 and 1-2, source 1. Start a breadth-first search from node 1, whose distance is 0. Node 1's neighbors are 0 and 2 (from the two edges) — neither has a distance yet, so both get distance 0 + 1 = 1. There are no more nodes left to explore (0 and 2 have no neighbors other than 1, which is already visited), so the search ends. The distances are dist[0] = 1, dist[1] = 0, dist[2] = 1, printed in node order as 1 0 1.

Approach

Because every edge counts as exactly one hop regardless of which nodes it connects, the nodes reachable in exactly 1 hop from the source are precisely its direct neighbors; the nodes reachable in exactly 2 hops are the neighbors of those neighbors that haven't already been reached in 1 hop or fewer; and so on. This "expand outward one ring of distance at a time" structure is exactly what breadth-first search (BFS) does.

Start a queue containing just the source, with dist[source] = 0 and every other distance marked as not yet known (for instance, -1, doubling as both "unknown" and the eventual answer for unreachable nodes). Repeatedly take a node off the front of the queue and look at each of its neighbors. Any neighbor that still has no distance recorded is being reached here for the first time — set its distance to the current node's distance plus 1, and add it to the back of the queue so its own neighbors get explored later. A neighbor that already has a distance recorded has already been reached by some earlier, equally short or shorter path, so it's simply skipped.

The reason a node's distance is only ever set once, on its first visit, is exactly why that distance is guaranteed to be the shortest one: BFS processes nodes in order of increasing distance from the source (all distance-0 nodes are dequeued before any distance-1 node is even discovered, all distance-1 nodes before any distance-2 node, and so on), so the first time any node is reached is necessarily via a shortest possible path to it. Once the queue empties, every node that was ever reachable has its correct shortest distance recorded, and every node whose distance is still unset is genuinely unreachable from the source, so it keeps the placeholder value of -1.

Common Mistakes

• Using depth-first search (DFS) instead of BFS. DFS explores as far as possible down one path before backtracking, so the first time it reaches a node is not necessarily via the shortest path — recording a node's "distance" as however deep the DFS happened to be when it first got there can overstate the true shortest distance.
• Forgetting that the graph is undirected. Each edge u v needs to be added to both u's neighbor list and v's neighbor list. Only adding it in one direction silently turns the graph directed, and can make some genuinely reachable nodes appear unreachable depending on which direction the edge happened to be listed in the input.
• Re-adding a node to the queue every time it's seen as a neighbor, instead of only the first time. If a node's distance isn't checked (and set) before it's enqueued, the same node can be enqueued multiple times from different neighbors, wasting time and — if its distance then gets overwritten on a later, longer path — potentially reporting the wrong distance instead of the shortest one.