Shortest Distances in an Unweighted Graph
easyGraphs II+10 XPTime limit 2s
A metro map has n stations and m two-way lines, each joining two stations; every ride between neighbouring stations counts as one hop. Starting from station s, find the minimum number of hops to every station.
Input:
- line 1:
n m s - next
mlines:u v
Output: one line with n numbers: the distance from s to stations 1, 2, …, n (distance to s itself is 0; print -1 for a station that cannot be reached).
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, u ≠ v, no repeated lines.
Think about it: in an unweighted graph, BFS visits nodes in order of distance — the first time you reach a node is along a shortest path. Each node and edge is handled once: O(n + m). No Dijkstra needed.
Sample input 1
5 5 1 1 2 1 3 2 4 3 4 4 5
Sample output 1
0 1 1 2 3
Sample input 2
4 1 2 1 2
Sample output 2
1 0 -1 -1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).