Skills101
← All coding problems

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 m lines: 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).

Loading editor…

Log in to run and submit your code — it's free.