Editorial for BFS Shortest Distances

Use this editorial only when stuck, and do not 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$ .

BFS processes vertices in increasing order of distance from $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)$ . The memory complexity is $O(n + m)$ .

Solution (Python)

Code 1

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()

Comments0

No comments yet

Be the first to comment.

Editorial for BFS Shortest Distances

Approach

Solution (Python)

Comments0

New comment