Editorial for BFS Shortest Distances

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Use breadth-first search from the starting vertex $s$ ~s~.

BFS processes vertices in increasing order of distance from $s$ ~s~. When we first discover a vertex, the path used to reach it has the minimum possible number of edges, so we store that distance and push the vertex into the queue. Vertices that remain undiscovered after BFS are unreachable and keep distance -1.

Each vertex is enqueued at most once and each undirected edge is inspected twice, so the time complexity is $O(n + m)$ ~O(n + m)~. The memory complexity is $O(n + m)$ ~O(n + m)~.

Solution (Python)

import sys
from collections import deque


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m, s = data[0], data[1], data[2] - 1
    graph = [[] for _ in range(n)]
    pos = 3
    for _ in range(m):
        a = data[pos] - 1
        b = data[pos + 1] - 1
        pos += 2
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * n
    dist[s] = 0
    queue: deque[int] = deque([s])

    while queue:
        v = queue.popleft()
        next_dist = dist[v] + 1
        for to in graph[v]:
            if dist[to] == -1:
                dist[to] = next_dist
                queue.append(to)

    sys.stdout.write(" ".join(map(str, dist)) + "\n")


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.